Xpress-SLP Structures

Topics covered in this chapter:

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 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.

Xpress-SLP Matrix Name Generation

Xpress-SLP adds rows and columns to the nonlinear problem in order to create a linear approximation. The new rows and columns are given names derived from the row or column to which they are related as follows:

Row or column type	Control parameter containing format	Default format
Update row	XSLP_UPDATEFORMAT	pU_r
Delta vector	XSLP_DELTAFORMAT	pD_c
Penalty delta (below step bound)	XSLP_MINUSDELTAFORMAT	pD-c
Penalty delta (above step bound)	XSLP_PLUSDELTAFORMAT	pD+c
Penalty error (below RHS)	XSLP_MINUSERRORFORMAT	pE-r
Penalty error (above RHS)	XSLP_PLUSERRORFORMAT	pE+r
Row for total of all penalty vectors (error or delta)	XSLP_PENALTYROWFORMAT	pPR_x
Column for standard penalty cost (error or delta)	XSLP_PENALTYCOLFORMAT	pPC_x
LO step bound formulated as a row	XSLP_SBLOROWFORMAT	pSB-c
UP step bound formulated as a row	XSLP_SBUPROWFORMAT	pSB+c

In the default formats:

p

a unique prefix (one or more characters not used as the beginning of any name in the problem).

r

the original row name.

c

the original column name.

x

The penalty row and column vectors are suffixed with "ERR" or "DELT" (for error and delta respectively).

Other characters appear "as is".

The format of one of these generated names can be changed by setting the corresponding control parameter to a formatting string using standard "C"-style conventions. In these cases, the unique prefix is not available and the only obvious choices, apart from constant names, use "%s" to include the original name — for example:

 U_%s would create names like U_abcdefghi
 U_%-8s would create names like U_abcdefgh (always truncated to 8 characters).

You can use a part of the name by using the XSLP_*OFFSET control parameters (such as XSLP_UPDATEOFFSET) which will offset the start of the original name by the number of characters indicated (so, setting XSLP_UPDATEOFFSET to 1 would produce the name U_bcdefghi).

Xpress-SLP Statistics

When a matrix is read in using XSLPreadprob, statistics on the model are produced. They should be interpreted as described in the numbered footnotes:

Reading Problem xxx                                               (1)
Problem Statistics
        1920 (      0 spare) rows                                 (2)
         899 (      0 spare) structural columns                   (3)
        6683 (   3000 spare) non-zero elements                    (4)
MIP Entity Statistics
      0 entities   0 sets    0 set members                        (5)
Xpress-SLP Statistics:
        3632 coefficients                                         (6)
          14 extended variable arrays                             (7)
           1 user functions                                       (8)
        1011 SLP variables                                        (9)

Notes:

1. Standard output from XPRSreadprob reading the linear part of the problem
2. Number of rows declared in the ROWS section
3. Number of columns with at least one constant coefficient
4. Number of constant elements
5. Integer and SOS statistics if appropriate
6. Number of non-constant coefficients
7. Number of XVs defined
8. Number of user functions defined
9. Number of variables identified as SLP variables (interacting with a non-linear coefficient)

When the original problem is augmented prior to optimization, the following statistics are produced:

Xpress-SLP Augmentation Statistics:	
  Columns:	
         754 implicit SLP variables                              (10)
        1010 delta vectors                                       (11)
        2138 penalty error vectors (1177 positive, 961 negative) (12)
  Rows:	
        1370 nonlinear constraints                               (13)
        1010 update rows                                         (14)
           1 penalty error rows                                  (15)
  Coefficients:	
       11862 non-constant coefficients                           (16)

Notes:

10. SLP variables appearing only in coefficients and having no constant elements
11. Number of delta vectors created
12. Numbers of penalty error vectors
13. Number of constraints containing nonlinear terms
14. Number of update rows (equals number of delta vectors)
15. Number of rows totaling penalty vectors (error or delta)
16. Number of non-constant coefficients in the linear augmented matrix

If the matrix is read in using the XPRSloadxxx and XSLPloadxxx functions then these statistics may not be produced. However, most of the values are accessible through Xpress NonLinear integer attributes using the XSLPgetintattrib function.

SLP Variable History

Xpress-SLP maintains a history value for each SLP variable. This value indicates the direction in which the variable last moved and the number of consecutive times it moved in the same direction. All variables start with a history value of zero.

Current History	Change in activity of variable	New History
0	>0	1
0	<0	-1
>0	>0	No change unless delta vector is at its bound. If it is, then new value is Current History + 1
>0	<0	-1
<0	<0	No change unless delta vector is at its bound. If it is, then new value is Current History - 1
<0	>0	1
anything	0	No change

Tests of variable movement are based on comparison with absolute and relative (and, if set, closure) tolerances. Any movement within tolerance is regarded as zero.

If the new absolute value of History exceeds the setting of XSLP_SAMECOUNT, then the step bound is reset to a larger value (determined by XSLP_EXPAND) and History is reset as if it had been zero.

If History and the change in activity are of opposite signs, then the step bound is reset to a smaller value (determined by XSLP_SHRINK) and History is reset as if it had been zero.

With the default settings, History will normally be in the range -1 to -3 or +1 to +3.