Extended MPS file format

Topics covered in this chapter:

One method of inputting a problem to Xpress NonLinear is from a text file which is similar to the normal MPS format matrix file. The Xpress NonLinear file uses free format MPS-style data. All the features of normal free-format MPS are supported. There are no changes to the sections except as indicated below.

Note: the use of free-format requires that no name in the matrix contains any leading or embedded spaces and that no name could be interpreted as a number. Therefore, the following names are invalid:

B 02

because it contains an embedded space;

1E02

because it could be interpreted as 100 (the scientific or floating-point format number, 1.0E02).

It is possible to use column and row names including mathematical operators. A variable name a+b is valid. However, as an expression a + b would be interpreted as the addition of variables a and b - note the spaces between the variable names - it is best practice to avoid such names when possible. SLP will produce a warning if such names are encountered in the MPS file.

Formulae

One new feature of the Extended MPS format is the formula. A formula is written in much the same way as it would be in any programming language or spreadsheet. It is made up of (for example) constants, functions, the names of variables, and mathematical operators. The formula always starts with an equals sign, and each item (or token) is separated from its neighbors by one or more spaces.

Tokens may be one of the following:

• A constant;
• The name of a variable;
• An arithmetic operator "+", "-", "*", "/";
• The exponentiation operator "**" or "^";
• An opening or closing bracket "(" or ")";
• A comma "," separating a list of function arguments;
• The name of a supported internal function such as LOG, SIN, EXP;
• The name of a user-supplied function;
• A colon ":" preceding the return argument indicator of a multi-valued function;
• The name of a return argument from a multi-valued function.

The following are valid formulae:

= SIN ( A / B )

SIN is a recognized internal function which takes one argument and returns one result (the sin of its argument).

= A ^ B

^ is the exponentiation symbol. Note that the formula may have valid syntax but it still may not be possible to evaluate it (for example if A = -1 and B = 0.5).

= MyFunc1 ( C1 , - C2 , C3 : 1 )

MyFunc1 must be a function which can take three arguments and which returns an array of results. This formula is asking for the first item in the array.

The following are not valid formulae:

SIN ( A )

Missing the equals sign at the start

=SIN(A)

No spaces between adjacent tokens

= A * * B

"**" is exponentiation, "* *" (with an embedded space) is not a recognized operation.

= MyFunc1 ( C1 , - C2 , C3 , 1 )

If MyFunc1 is as shown in the previous set of examples, it returns an array of results. The last argument to the function must be delimited by a colon, not a comma, and is the name or number of the item to be returned as the value of the function.

There is no limit to the length of a formula. However, parsing very long records can be slow, and consideration should be given to pre-parsing them and passing the parsed formula to Xpress NonLinear rather than asking it to parse the formula itself.

COLUMNS

Normal MPS-style records of the form

column    row1    value1    [  row2    value2  ]

are supported. Non-linear relationships are modeled by using a formula instead of a constant in the value1 field. If a formula is used, then only one coefficient can be described in the record (that is, there can be no row2 value2). The formula begins with an equals sign ("=") and is as described in the previous section.

A formula must be contained entirely on one record.

Variables used in formulae may be included in the COLUMNS section as variables, or may exist only as items within formulae. A variable which exists only within formulae is called an implicit variable.

Sometimes the non-linearity cannot be written as a coefficient. For example, in the constraint
Y - LOG(X) = 0,
LOG(X) cannot be written in the form of a coefficient. In such a case, the reserved column name "=" may be used in the first field of the record as shown:

Y	MyRow	1
=	MyRow	= - LOG ( X )

Effectively, "=" is a column with a fixed activity of 1.0 .

When a file is read by XSLPreadprob, more than one coefficient can be defined for the same column/row intersection. As long as there is at most one constant coefficient (one not written as a formula), the coefficients will be added together. If there are two or more constant coefficients for the same intersection, they will be handled by the Optimizer according to its own rules (normally additive, but the objective function retains only the last coefficient).

BOUNDS

Bounds can be included for variables which are not defined explicitly in the COLUMNS section of the matrix. If they are not in the COLUMNS section, they must appear as variables within formulae (implicit variables). A BOUNDS entry for an item which is not a column or a variable will produce a warning message and will be ignored.

MIP entities (such as integer variables and members of Special Ordered Sets) must be defined explicitly in the COLUMNS section of the matrix. If a variable would otherwise appear only in formulae in coefficients, then it should be included in the COLUMNS section with a zero entry in a row (for example, the objective function) which will not affect the result.

SLPDATA

SLPDATA is a new section which holds additional information for solving the non-linear problem using SLP.

Many of the data items have a setname. This works in the same way as the BOUND, RANGE or RHS name, in that a number of different values can be given, each with a different set name, and the one which is actually used is then selected by specifying the appropriate setname before reading the problem.

Record type IV and the tolerance records Tx, Rx can have "=" as the variable name. This provides a default value for the record type, which will be used if no specific information is given for a particular variable.

Note that only linear BOUND types can be included in the SLPDATA section. Bound types for MIP entities (discrete variables and special ordered sets) must be provided in the normal BOUNDS section and the variables must also appear explicitly in the COLUMNS section.

All of the items in the SLPDATA section can be loaded into a model using Xpress NonLinear function calls.

DR (Determining row)

DR  variable  rowname  [weighting]  [limit]

The DR record defines the determining row for a variable.

In most non-linear problems, there are some variables which are effectively defined by means of an equation in terms of other variables. Such an equation is called a determining row. If Xpress NonLinear knows the determining rows for the variables which appear in coefficients, then it can provide better linear approximations for the problem and can then solve it more quickly. Optionally, a non-zero integer value can be included in the weighting field. Variables which have weights will generally be evaluated in order of increasing weight. Variables without weights will generally be evaluated after those which do have weights. However, if a variable A (with or without a weight) is dependent through its determining row on another variable B, then B will always be evaluated first. The optional limit field provides a variable specific value for XSLP_CASCADENLIMIT.

Example:

DR  X  Row1
This defines Row1 as the determining row for the variable X. If Row1 is
X - Y * Z = 6
then Y and Z will be recalculated first before X is recalculated as Y*Z+6.

EC (Enforced constraint)

EC  rowname

The EC record defines an enforced constraint. Penalty error vectors are never added to enforced constraints, so the effect of such constraints is maintained at all times.

Note that this means the linearized version of the enforced constraint will be active, so it is important to appreciate that enforcing too many constraints can easily lead to infeasible linearizations which will make it hard to solve the original nonlinear problem.

Example:

EC  Row1
This defines Row1 as an enforced constraint. When the SLP is augmented, no penalty error vectors will be added to the constraint, so the linearized version of Row1 will constrain the linearized problem in the same sense (L, G or E) as the nonlinear version of Row1 constrains the original nonlinear problem.

FR (Free variable)

FR  boundname  variable

An FR record performs the same function in the SLPDATA section as it does in the BOUNDS section. It can be used for bounding variables which do not appear as explicit columns in the matrix.

FX (Fixed variable)

FX  boundname  variable  value

An FX record performs the same function in the SLPDATA section as it does in the BOUNDS section. It can be used for bounding variables which do not appear as explicit columns in the matrix.

IV (Initial value)

IV  setname  variable  [value  |  = formula]

An IV record specifies the initial value for a variable. All variables which appear in coefficients or terms, or which have non-linear coefficients, should have an IV record.

A formula provided as the initial value for a variable can contain references to other variables. It will be evaluated based on the initial values of those variables (which may themselves be calculated by formula). It is the user's responsibility to ensure that there are no circular references within the formulae. Formulae are typically used to calculate consistent initial values for dependent variables based on the values of independent variables.

If an IV record is provided for the equals column (the column whose name is "=" and which has a fixed value of 1.0), the value provided will be used for all SLP variables which do not have an explicit initial value of their own.

If there is no explicit or implied initial value for an SLP variable, the value of control parameter XSLP_DEFAULTIV will be used.

If the initial value is greater than the upper bound of the variable, the upper bound will be used; if the initial value is less than the lower bound of the variable, the lower bound will be used.

If both a formula and a value are provided, then the explicit value will be used.

Example:

IV  IVSET1  Col99  1.4971
IV  IVSET2  Col99  2.5793
This sets the initial value of column Col99. The initial value to be used is selected using control parameter XSLP_IVNAME. If no selection is made, the first initial value set found will be used.

If Col99 is bounded in the range 1≤Col99≤2 then in the second case (when IVSET2 is selected), an initial value of 2 will be used because the value given is greater than the upper bound.

IV  IVSET2  Col98  = Col99 * 2
This sets the value of Col98 to twice the initial value of Col99 when IVSET2 is the selected initial value set.

LO (Lower bounded variable)

LO  boundname  variable  value

A LO record performs the same function in the SLPDATA section as it does in the BOUNDS section. It can be used for bounding variables which do not appear as explicit columns in the matrix.

Rx, Tx (Relative and absolute convergence tolerances)

Rx  setname  variable  value

Tx  setname  variable  value

The Tx and Rx records (where "x" is one of the defined tolerance types) define specific tolerances for convergence of the variable. See the section "convergence criteria" for a list of convergence tolerances. The same tolerance set name (setname) is used for all the tolerance records.

Example:

RA  TOLSET1  Col99  0.005
TA  TOLSET1  Col99  0.05
RI  TOLSET1  Col99  0.015
RA  TOLSET1  Col01  0.01
RA  TOLSET2  Col01  0.015
These records set convergence tolerances for variables Col99 and Col01. Tolerances RA (relative convergence tolerance), TA (absolute convergence tolerance) and RI (relative impact tolerance) are set for Col99 using the tolerance set named TOLSET1.
Tolerance RA is set for variable Col01 using tolerance sets named TOLSET1 and TOLSET2.
If control parameter XSLP_TOLNAME is set to the name of a tolerance set before the problem is read using XSLPreadprob, then only the tolerances on records with that tolerance set will be used. If XSLP_TOLNAME is blank or not set, then the name of the set on the first tolerance record will be used.

SB (Initial step bound)

SB  setname  variable  value

An SB record defines the initial step bounds for a variable. Step bounds are symmetric (i.e. the bounds on the delta are -SB≤delta≤+SB). If a value of 1.0E+20 is used (equivalent to XPRS_PLUSINFINITY in programming), the delta will never have step bounds applied, and will almost always be regarded as converged.

If there is no explicit initial step bound for an SLP variable, a value will be estimated either from the size of the coefficients in the initial linearization, or from the values of the variable during the early SLP iterations. The value of control parameter XSLP_DEFAULTSTEPBOUND provides a lower limit for the step bounds in such cases.

If there is no explicit initial step bound, then the closure convergence tolerance cannot be applied to the variable.

Example:

SB  SBSET1  Col99  1.5
SB  SBSET2  Col99  7.5
This sets the initial step bound of column Col99. The value to be used is selected using control parameter XSLP_SBNAME. If no selection is made, the first step bound set found will be used.

UF (User function)

UF  funcname  = libraryname  ( functiontype )  linkage  = library

A UF record defines a user function.
The definition includes the function's type which matches the parameter supplied to the adduserfunction call.

Example:

UF  MyFunc  (  VECMAPDELTA  )  DLL  =  UserLib
This defines a user function called MyFunc that takes multiple input arguments and supplies its own derivatives. The linkage is DLL (free-standing user library or DLL) and the function is in file UserLib.

UP (Free variable)

UP  boundname  variable  value

An UP record performs the same function in the SLPDATA section as it does in the BOUNDS section. It can be used for bounding variables which do not appear as explicit columns in the matrix.

WT (Explicit row weight)

WT  rowname  value

The WT record is a way of setting the initial penalty weighting for a row. If value is positive, then the default initial weight is multiplied by the value given. If value is negative, then the absolute value will be used instead of the default weight.

Increasing the penalty weighting of a row makes it less attractive to violate the constraint during the SLP iterations.

Examples:

WT  Row1  3
This changes the initial weighting on Row1 by multiplying by 3 the default weight calculated by Xpress-SLP during problem augmentation.

WT  Row1  -3
This sets the initial weighting on Row1 to 3.

DL (variable specific Determining row cascade iteration Limit)

DL  columnname  limit

A DL record specififies a variable specific iteration limit to be emposed on the number of iterations when cascading the variable. This can be used to overwrite the setting of XSLP_CASCADENLIMIT for a specific variable.