SLP Matrix Structures

Xpress-SLP augments the original matrix to include additional rows and columns to model some or all of the variables involved in nonlinear relationships, together with first-order derivatives.

The amount and type of augmentation is determined by the bit map control variable XSLP_AUGMENTATION:

Bit 0

Minimal augmentation. All SLP variables appearing in coefficients or matrix entries are provided with a corresponding update row and delta vector.

Bit 1

Even-handed augmentation. All nonlinear expressions are converted into terms. All SLP variables are provided with a corresponding update row and delta vector.

Bit 2

Create penalty error vectors (+ and -) for each equality row of the original problem containing a nonlinear coefficient or term. This can also be implied by the setting of bit 3.

Bit 3

Create penalty error vectors (+ and/or - as required) for each row of the original problem containing a nonlinear coefficient or term. Setting bit 3 to 1 implies the setting of bit 2 to 1 even if it is not explicitly carried out.

Bit 4

Create additional penalty delta vectors to allow the solution to exceed the step bounds at a suitable penalty.

Bit 8

Implement step bounds as constraint rows.

Bit 9

Create error vectors (+ and/or - as required) for each constraining row of the original problem.

If Bits 0-1 are not set, then Xpress-SLP will use standard augmentation: all SLP variables (appearing in coefficients or matrix entries, or variables with non constant coefficients) are provided with a corresponding update row and delta vector.

To avoid too many levels of super- and sub- scripting, we shall use X, Y and Z as variables, F() as a function, and R as the row name. In the matrix structure, column and row names are shown in italics.

X₀ is the current estimate ("assumed value") of X. F'_x(...) is the first derivative of F with respect to X.

Augmentation of a nonlinear coefficient

Original matrix structure

	X
R	F(Y,Z)

Matrix structure: minimal augmentation (XSLP_AUGMENTATION=1)

	X	Y	Z	dY	dZ
R	F(Y0,Z0)			X0*F'y(Y0,Z0)	X0*F'z(Y0,Z0)
uY		1		-1		=	Y0
uZ			1		-1	=	Z0

The original nonlinear coefficient (X,R) is replaced by its evaluation using the assumed values of the independent variables.

Two vectors and one equality constraint for each independent variable in the coefficient are created if they do not already exist.

The new vectors are:

• The SLP variable (e.g. Y)
• The SLP delta variable (e.g. dY)

The new constraint is the SLP update row (e.g. uY) and is always an equality. The only entries in the update row are the +1 and -1 for the SLP variable and delta variable respectively. The right hand side is the assumed value for the SLP variable.

The entry in the original nonlinear constraint row for each independent variable is the first-order partial derivative of the implied term X*F(Y,Z), evaluated at the assumed values.

The delta variables are bounded by the current values of the corresponding step bounds.

Matrix structure: standard augmentation (XSLP_AUGMENTATION=0)

	X	Y	Z	dX	dY	dZ
R	F(Y0,Z0)				X0*F'y(Y0,Z0)	X0*F'z(Y0,Z0)
uX	1			-1			=	X0
uY		1			-1		=	Y0
uZ			1			-1	=	Z0

The original nonlinear coefficient (X,R) is replaced by its evaluation using the assumed values of the independent variables.

Two vectors and one equality constraint for each independent variable in the coefficient are created if they do not already exist.

The new vectors are:

• The SLP variable (e.g. Y)
• The SLP delta variable (e.g. dY)

The new constraint is the SLP update row (e.g. uY) and is always an equality. The only entries in the update row are the +1 and -1 for the SLP variable and delta variable respectively. The right hand side is the assumed value for the SLP variable.

The entry in the original nonlinear constraint row for each independent variable is the first-order partial derivative of the implied term X*F(Y,Z), evaluated at the assumed values.

The delta variables are bounded by the current values of the corresponding step bounds.

One new vector and one new equality constraint are created for the variable containing the nonlinear coefficient.

The new vector is:

• The SLP delta variable (e.g. dX)

The new constraint is the SLP update row (e.g. uX) and is always an equality. The only entries in the update row are the +1 and -1 for the original variable and delta variable respectively. The right hand side is the assumed value for the original variable.

The delta variable is bounded by the current values of the corresponding step bounds.

Matrix structure: even-handed augmentation (XSLP_AUGMENTATION=2)

	=	X	Y	Z	dX	dY	dZ
R	X0*F(Y0,Z0)				F(Y0,Z0)	X0*F'y(Y0,Z0)	X0*F'z(Y0,Z0)
uX		1			-1			=	X0
uY			1			-1		=	Y0
uZ				1			-1	=	Z0

The coefficient is treated as if it was the term X*F(Y,Z) and is expanded in the same way as a nonlinear term.

Augmentation of a nonlinear term

Original matrix structure

	=
R	F(X,Y,Z)

The column name = is a reserved name for a column which has a fixed activity of 1.0 and can conveniently be used to hold nonlinear terms, particularly those which cannot be expressed as coefficients of variables.

Matrix structure: all augmentations

	=	X	Y	Z	dX	dY	dZ
R	F(X0,Y0,Z0)				F'x(X0,Y0,Z0)	F'y(X0,Y0,Z0)	F'z(X0,Y0,Z0)
uX		1			-1			=	X0
uY			1			-1		=	Y0
uZ				1			-1	=	Z0

The original nonlinear coefficient (=,R) is replaced by its evaluation using the assumed values of the independent variables.

Two vectors and one equality constraint for each independent variable in the coefficient are created if they do not already exist.

The new vectors are:

• The SLP variable (e.g. Y)
• The SLP delta variable (e.g. dY)

The new constraint is the SLP update row (e.g. uY) and is always an equality. The only entries in the update row are the +1 and -1 for the SLP variable and delta variable respectively. The right hand side is the assumed value for the SLP variable.

The entry in the original nonlinear constraint row for each independent variable is the first-order partial derivative of the term F(X,Y,Z), evaluated at the assumed values.

The delta variables are bounded by the current values of the corresponding step bounds.

One new vector and one new equality constraint are created for the variable containing the nonlinear coefficient.

The new vector is:

• The SLP delta variable (e.g. dX)

The new constraint is the SLP update row (e.g. uX) and is always an equality. The only entries in the update row are the +1 and -1 for the original variable and delta variable respectively. The right hand side is the assumed value for the original variable.

The delta variable is bounded by the current values of the corresponding step bounds.

Note that if F(X,Y,Z) = X*F(Y,Z) then this translation is exactly equivalent to that for the nonlinear coefficient described earlier.

Augmentation of a user-defined SLP variable

Typically, this will arise when a variable represents the result of a nonlinear function, and is required to converge, or to be constrained by step-bounding to force convergence. In essence, it would arise from a relationship of the form
X = F(Y,Z)

Original matrix structure

	=	X
R	F(Y,Z)	-1

Matrix structure: all augmentations

	=	X	Y	Z	dX	dY	dZ
R	F(Y0,Z0)	-1				F'y(Y0,Z0)	F'z(Y0,Z0)
uX		1			-1			=	X0
uY			1			-1		=	Y0
uZ				1			-1	=	Z0

The Y,Z structures are identical to those which would result from a nonlinear term or coefficient. The X, dX and uX structures effectively define dX as the deviation of X from X0 which can be controlled with step bounds.

The augmented and even-handed structures include more delta vectors, and so allow for more measurement and control of convergence.

Type of structure	Minimal	Standard	Even-handed
Type of variable
Variables in nonlinear coefficients	Y	Y	Y
Variables with nonlinear coefficients	N	Y	Y
User-defined SLP variable	Y	Y	Y
Nonlinear term	Y	Y	Y

Y

SLP variable has a delta vector which can be measured and/or controlled for convergence.

N

SLP variable does not have a delta and cannot be measured and/or controlled for convergence.

There is no mathematical difference between the augmented and even-handed structures.

The even-handed structure is more elegant because it treats all variables in an identical way. However, the original coefficients are lost, because their effect is transferred to the "=" column as a term and so it is not possible to look up the coefficient value in the matrix after the SLP solution process has finished (whether because it has converged or because it has terminated for some other reason). The values of the SLP variables are still accessible in the usual way.

Some of the extended convergence criteria will be less effective because the effects of the individual coefficients may be amalgamated into one term (so, for example, the total positive and negative contributions to a constraint are no longer available).

SLP penalty error vectors

Bits 2, 3 and 9 of control variable XSLP_AUGMENTATION determine whether SLP penalty error vectors are added to constraints. Bit 9 applies penalty error vectors to all constraints; bits 2 and 3 apply them only to constraints containing nonlinear terms. When bit 2 or bit 3 is set, two penalty error vectors are added to each such equality constraint; when bit 3 is set, one penalty error vector is also added to each such inequality constraint. The general form is as follows:

Original matrix structure

	=
R	F(Y,Z)

Matrix structure with error vectors

	X	R+	R-
R	F(Y,Z)	+1	-1
P_ERROR		+Weight	+Weight

For equality rows, two penalty error vectors are added. These have penalty weights in the penalty error row P_ERROR, whose total is transferred to the objective with a cost of XSLP_CURRENTERRORCOST. For inequality rows, only one penalty error vector is added — the one corresponding to the slack is omitted. If any error vectors are used in a solution, the transfer cost from the cost penalty error row will be increased by a factor of XSLP_ERRORCOSTFACTOR up to a maximum of XSLP_ERRORMAXCOST.

Error vectors are ignored when calculating cascaded values.

The presence of error vectors at a non-zero level in an SLP solution normally indicates that the solution is not self-consistent and is therefore not a solution to the nonlinear problem.

Control variable XSLP_ERRORTOL_A is a zero tolerance on error vectors. Any error vector with a value less than XSLP_ERRORTOL_A will be regarded as having a value of zero.

Bit 9 controls whether error vectors are added to all constraints. If bit 9 is set, then error vectors are added in the same way as for the setting of bit 3, but to all constraints regardless of whether or not they have nonlinear coefficients.