The augmented matrix structure

During the augmentation process, Xpress-SLP builds additional matrix structure to represent the linear approximation of the nonlinear constraints within the problem (see Xpress-SLP Structures). In effect, it adds a generic structure which approximates the effect of changes to variables in nonlinear expressions, over and above that which would apply if the variables were simply replaced by their current values.

As a very simple example, consider the nonlinear constraint (R1, say)
X * Y ≤ 10

The variables X and Y are replaced by X₀+δX and Y₀+δY respectively, where X₀ and Y₀ are the values of X and Y at which the approximation will be made.

The original constraint is therefore
(X₀+δX)*(Y₀+δY) ≤ 10

Expanding this into individual terms, we have
X₀*Y₀ + X₀*δY + Y₀*δX + δX*δY ≤ 10

The first term is constant, the next two terms are linear in δY and δX respectively, and the last term is nonlinear.

The augmented structure deletes the nonlinear term, so that the remaining structure is a linear approximation to the original constraint. The justification for doing this is that if δX or δY (or both) are small, then the error involved in ignoring the term is also small.

The resulting matrix structure has entries of Y₀ in the delta variable δX and X₀ in the delta variable δY. The constant entry X₀*Y₀ is placed in the special "equals" column which has a fixed activity of 1. All these entries are updated at each SLP iteration as the solution process proceeds and the problem is linearized at a new point. The positions of these entries – (R1,δX), (R1,δY) and (R1,=) – are known as placeholders.