XMPS Matrix Files

The FICO Xpress Optimizer accepts matrix files in LP or MPS format, and an extension of this, XMPS format. In that the latter represents a slight modification of the industry-standard, we provide details of it here.

XMPS format defines the following fields:

Field	1	2	3	4	5	6
Columns	2-3	5-12	15-22	25-36	40-47	50-61

The following sections are defined:

NAME	the matrix name;
ROWS	introduces the rows;
COLUMNS	introduces the columns;
QUADOBJ / QMATRIX	introduces a quadratic objective function;
QCMATRIX	introduces the quadratic constraints;
DELAYEDROWS	introduces the delayed rows;
MODELCUTS	introduces the model cuts;
INDICATORS	introduces the indicator contraints;
SETS	introduces SOS definitions;
RHS	introduces the right hand side(s);
RANGES	introduces the row ranges;
BOUNDS	introduces the bounds;
ENDATA	signals the end of the matrix.
compatibility	additional sections for extensions of the MPS format that can be read but not written.

All section definitions start in column 1.

NAME section

Format:	Cols 1-4	Field 3
	NAME	model_name

ROWS section

Format:	Cols 1-4
	ROWS

followed by row definitions in the format:

Field 1	Field 2
type	row_name

The row types (Field 1) are:

N	unconstrained (for objective functions);
L	less than or equal to;
G	greater than or equal to;
E	equality.

COLUMNS section

Format:	Cols 1-7
	COLUMNS

followed by columns in the matrix in column order, i.e. all entries for one column must finish before those for another column start, where:

Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
blank	col	row1	value1	row2	value2

specifies an entry of value1 in column col and row row1 (and value2 in col and row row2). The Field 5/Field 6 pair is optional.

QUADOBJ / QMATRIX section (Quadratic Programming only)

A quadratic objective function can be specified in an MPS file by including a QUADOBJ or QMATRIX section. For fixed format XMPS files, the section format is as follows:

Format:	Cols 1-7
	QUADOBJ

or

Format:	Cols 1-7
	QMATRIX

followed by a description of the quadratic terms. For each quadratic term, we have:

Field 1	Field 2	Field 3	Field 4
blank	col1	col2	value

where col1 is the first variable in the quadratic term, col2 is the second variable and value is the associated coefficient from the Q matrix. In the QMATRIX section all nonzero Q elements must be specified. In the QUADOBJ section only the nonzero elements in the upper (or lower) triangular part of Q should be specified. In the QMATRIX section the user must ensure that the Q matrix is symmetric, whereas in the QUADOBJ section the symmetry of Q is assumed and the missing part is generated automatically.

Note that the Q matrix has an implicit factors of 0.5 when included in the objective function.
This means, for instance that an objective function of the form

5x² + 7xy + 9y²

is represented in a QUADOBJ section as:

QUADOBJ
x      x      10
x      y       7
y      y      18

(The additional term 'y x 7' is assumed which is why the coefficient is not doubled); and in a QMATRIX section as:

QMATRIX
x      x      10
x      y       7
y      x       7
y      y      18

The QUADOBJ and QMATRIX sections must appear somewhere after the COLUMNS section and must only contain columns previously defined in the columns section. Columns with no elements in the problem matrix must be defined in the COLUMNS section by specifying a (possibly zero) cost coefficient.

QCMATRIX section (Quadratic Constraint Programming only)

Quadratic constraints may be added using QCMATRIX sections.

Format:	Cols 1-8	Field 3
	QCMATRIX	row_name

Each constraint having quadratic terms should have it's own QCMATRIX section. The QCMATRIX section exactly follows the description of the QMATRIX section, i.e. for each quadratic term, we have:

Field 1	Field 2	Field 3	Field 4
blank	col1	col2	value

where col1 is the first variable in the quadratic term, col2 is the second variable and value is the associated coefficient from the Q matrix. All nonzero Q elements must be specified. The user must ensure that the Q matrix is symmetric. For instance a constraint of the form

qc1: x+5x² + 7xy + 9y² <= 2

is represented as:

NAME example
ROWS
 L qc1
COLUMNS
   x      qc1     1
   y      qc1     0
QCMATRIX qc1
   x      x       5
   x      y       3.5
   y      x       3.5
   y      y       9
RHS
 RHS1     qc1     2
END

The QCMATRIX sections must appear somewhere after the COLUMNS section and must only contain columns previously defined in the columns section. Columns with no elements in the problem matrix must be defined in the COLUMNS section by specifying a (possibly zero) cost coefficient. QCMATRICES must be defined only for rows of type L or G and must have no range value defined in the RANGE section.

Note that the FICO Xpress Optimizer can only solve convex (MI)QPs. Thus the quadratic matrix should be positive semi-definite for <= rows and negative semi-definite for >= rows so that the defined region is convex. Otherwise the problem will need to be solved by the nonlinear solver.

NOTE: technically, there is one exception for the restriction on the row type being L or G. If the row is the first nonbinding row (type N) then the section is treated as a QMATRIX section instead. Please be aware, that this also means that the objective specific implied divider of 2 will be assumed (Q matrix has an implicit factors of 0.5 when included in the objective function, see the QMATRIX section). It's probably much better to use the QMATRIX or QUADOBJ sections to define quadratic objectives.

NOTE:

DELAYEDROWS section

This specifies a set of rows in the matrix that will be treated as delayed rows during a global search. These are rows that must be satisfied for any integer solution, but will not be loaded into the active set of constraints until required.

This section should be placed between the ROWS and COLUMNS sections. A delayed row may be of type L, G or E. Each row should appear either in the ROWS or the DELAYEDROWS section, not in both. Otherwise, the format used is the same as of the ROWS section.

Format:	Cols 1-11
	DELAYEDROWS

followed by row definitions in the format:

Field 1	Field 2
type	row_name

NOTE: For compatibility reasons, section names DELAYEDROWS and LAZYCONS are treated as synonyms.

MODELCUTS section

This specifies a set of rows in the matrix that will be treated as model cuts during a global search. During presolve the model cuts are removed from the matrix. Following optimization, the violated model cuts are added back into the matrix and the matrix is re-optimized. This continues until no violated cuts remain. This section should be placed between the ROWS and COLUMNS sections. Model cuts may be of type L, G or E. The model cuts must be "true" model cuts, in the sense that they are redundant at the optimal MIP solution. The Optimizer does not guarantee to add all violated model cuts, so they must not be required to define the optimal MIP solution.

Each row should appear either in the ROWS, DELAYEDROWS or in the MODELCUTS section, not in any two or three of them. Otherwise, the format used is the same as of the ROWS section.

Format:	Cols 1-9
	MODELCUTS

followed by row definitions in the format:

Field 1	Field 2
type	row_name

NOTE: A problem is not allowed to consists solely from model cuts. For compatibility reasons, section names MODELCUTS and USERCUTS are treated as synonyms.

INDICATORS section

This specifies that a set of rows in the matrix will be treated as indicator constraints during a global search. These are constraints that must be satisfied only when their associated controlling binary variables have specified values (either 0 or 1).

This section should be placed after any QUADOBJ, QMATRIX or QCMATRIX sections. The section format is as follows:

Format:	Cols 1-10
	INDICATORS

Subsequent records give the associations between rows and the controlling binary columns, with the following form:

Field 1	Field 2	Field 3	Field 4
type	row_name	col_name	value

which specifies that the row row_name must be satisfied only when column col_name has value value. Here type must always be IF and value can be either 0 or 1. Also referenced rows must be of type L or G only, and referenced columns must be binary.

SETS section (Integer Programming only)

Format:	Cols 1-4
	SETS

This record introduces the section which specifies any Special Ordered Sets. If present it must appear after the COLUMNS section and before the RHS section. It is followed by a record which specifies the type and name of each set, as defined below.

Field 1	Field 2
type	set

Where type is S1 for a Special Ordered Set of type 1 or S2 for a Special Ordered Set of type 2 and set is the name of the set.

Subsequent records give the set members for the set and are of the form:

Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
blank	set	col1	value1	col2	value2

which specifies a set member col1 with reference value value1 (and col2 with reference value value2). The Field 5/Field 6 pair is optional.

RHS section

Format:	Col 1-3
	RHS

followed by the right hand side as defined below:

Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
blank	rhs	row1	value1	row2	value2

specifies that the right hand side column is called rhs and has a value of value1 in row row1 (and a value of value2 in row row2). The Field 5/Field 6 pair is optional.

RANGES section

Format:	Cols 1-6
	RANGES

followed by the right hand side ranges defined as follows:

Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
blank	rng	row1	value1	row2	value2

specifies that the right hand side range column is called rng and has a value of value1 in row row1 (and a value of value2 in row row2). The Field 5/Field 6 pair is optional.

For any row, if b is the value given in the RHS section and r the value given in the RANGES section, then the activity limits below are applied:

Row Type	Sign of r	Upper Limit	Lower Limit
G	+	b+r	b
L	+	b	b-r
E	+	b+r	b
E	-	b	b+r

BOUNDS section

Format:	Cols 1-6
	BOUNDS

followed by the bounds acting on the variables:

Field 1	Field 2	Field 3	Field 4
type	blank	col	value

The Linear Programming bound types are:

UP	for an upper bound;
LO	for a lower bound;
FX	for a fixed value of the variable;
FR	for a free variable;
MI	for a non-positive ('minus') variable;
PL	for a non-negative ('plus') variable (the default).

There are six additional bound types specific to Integer Programming:

UI	for an upper bounded general integer variable;
LI	for a lower bounded general integer variable;
BV	for a binary variable;
SC	for a semi-continuous variable;
SI	for a semi-continuous integer variable;
PI	for a partial integer variable.

The value specified is an upper bound on the largest value the variable can take for types UP, FR, UI, SC and SI; a lower bound for types LO and LI; a fixed value for type FX; and ignored for types BV, MI and PL. For type PI it is the switching value: below which the variable must be integer, and above which the variable is continuous. If a non-integer value is given with a UI or LI type, only the integer part of the value is used.

• Integer variables may only take integer values between 0 and the upper bound. Integer variables with an upper bound of unity are treated as binary variables.
• Binary variables may only take the values 0 and 1. Sometimes called 0/1 variables.
• Partial integer variables must be integral when they lie below the stated value, above that value they are treated as continuous variables.
• Semi-continuous variables may take the value zero or any value between a lower bound and some finite upper bound. By default, this lower bound is 1.0. Other positive values can be specified as an explicit lower bound. For example

  BOUNDS
  LO x 0.8
  SC x 12.3

  means that x can take the value zero or any value between 0.8 and 12.3.
• Semi-continuous integer variables may take the value zero or any integer value between a lower bound and some finite upper bound.

GENCONS section

Format:	Cols 1-7
	GENCONS

This record introduces the section which specifies any general constraints, namely min, max, and, or, abs, pwl constraints. If present it must appear after the COLUMNS section. It is followed by a record which specifies the type and name of each general constraint, as defined below.

Field 1	Field 2
type	name

Where type is MAX for a maximum-constraint, MIN for a minimum-constraint, AND for an and-constraint, OR for an or-constraint, ABS for an absolute-value-constraint or PWL for a piecewise linear constraint and name is the name of the general constraint.

Subsequent records for min/max/and/or/abs give the elements for the constraint and are of the form:

Field 1	Field 2
blank	col/val

For all general constraints, the first given element (which needs to be the name of a column) will be the so-called "resultant". For the max- and min-constraints, the resultant is followed by an arbitrary number of further column names or values, and the resultant should be the maximum/minimum of the remaining columns and values. For the and- and or-constraints the resultant is followed by an arbitrary number of further column names, where all the columns (including the resultant) need to be binary, and the resultant will be one if and only if all (and) or at least one (or) of the remaining variables are one. For the abs-constraint, the resultant should be followed by exactly one futher column name, and the resultant will take the absolute value of the other column.

As an example, the constraint z = max {x, y, 5.0} could be written as

 GENCONS
 MAX m1
    z
	x
	y
	5.0

For piecewise linear constraints the format is slightly different, consisting of exactly one line of the form:

Field 1	Field 2
col1	col2

and at least three lines of the form:

Field 1	Field 2
val1	val2

The first line defines the two variables that should be restricted by a piecewise linear relationship and the points given in the remaining lines will define the piecewise linear function, which is extended beyond the first and last point according to the slope of the previous ones. For instance the piecewise linear constraint

y = 0, if x < 0
y = x, if 0 <= x <= 5
y = 2x - 5, if 5 < x <= 10
y = 15, if x > 10

could be represented as:

 GENCONS
 PWL p1
    x  y
	-1 0
    0  0
	5  5
	10 15
	11 15

ENDATA section

Format:	Cols 1-6
	ENDATA

is the last record of the file.

Compatibility

The optimizer is also able to read in some further sections defined by extensions of the LP format. This includes the SOS section, which is a different way of writing down special ordered sets, and the following sections that offer different ways of formulating piecewise linear constraints and objectives:

PWLOBJ section

Piecewise linear objective functions may be added using PWLOBJ sections.

Format:	Cols 1-6
	PWLOBJ

The piecewise linear objective function is defined via its extreme points, i.e., the function itself is given by all convex combinations of neighboring extreme points as well as the infinite rays defined by the first two and last two points. Each row of the PWLOBJ section defines one extreme point for one column.

Field 1	Field 2	Field 3	Field 4
blank	col	value1	value2

where col is the variable whose objective contribution is defined through the piecewise linear function and value2 is the objective contribution if the variable takes value1. For instance the piecewise linear objective function

0, if x < 0
x, if 0 <= x <= 5
2x - 5, if 5 < x <= 10
15, if x > 10

could be represented as:

PWLOBJ
   x         -1 0
   x         0  0
   x         5  5
   x         10 15
   x         11 15

If there are piecewise linear objective functions for multiple variables, these should be given consecutively (i.e., first all extreme points for x, then all for y). Furthermore, for each variable, the extreme points should be sorted according to non-decreasing value1. The piecewise linear functions do not necessarily need to be continuous, in this case two extreme points with identical value1 and different value2 can be given and the first one will be used as the lefthand-limit and the second one as the righthand-limit. Note that for value1 itself, both value2 can appear in the solution due to tolerances.

PWLNAM section

PWLNAM is the first of the two sections defining piecewise linear constraints.

Format:	Cols 1-6
	PWLNAM

Similar to the piecewise linear objective, the piecewise linear constraints will mainly be defined through its extreme points, which happens in the PWLCON section. In addition to that, however, the two variables involved in the restriction y = f(x), with piecewise linear function f, need to be specified, and additionally a pre- and postslope are given, defining the slope of the piecewise linear function before the first and after the last extreme point. Each piecewise linear function needs to be named, to later refer to it in the PWLCON section when specifying the extreme points.

Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
blank	name	col1	col2	value1	value2

where col1 is the resulting variable (y above), col2 is the input variable (x above), value1 is the preslope defining the piecewise linear function up to the first extreme point and value1 is the postslope defining it after the last extreme point.

PWLCON section

PWLCON is the second of the two sections defining piecewise linear constraints.

Format:	Cols 1-6
	PWLCON

Each piecewise linear constraint introduced in the PWLNAM section needs to be further specified through its extreme points, defining the behaviour between the pre- and postlope. Each line consists of the name of a piecewise linear constraint introduced in the PWLNAM followed by a list of extreme points. Similar to the PWLOBJ section, the functions can be discontinuous, in which case the extreme points have to be given in the correct order.

Field 1	Field 2	Field 3	Field 4
blank	name	value1	value2

where name is the name of a piecewise linear function introduced in the PWLNAM section and value1 and value2 define an extreme point, where value1 is the value of the input variable and value1 is the corresponding output value. For instance the piecewise linear constraint

y = 0, if x < 0
y = x, if 0 <= x <= 5
y = 2x - 5, if 5 < x <= 10
y = 15, if x > 10

could be represented as:

PWLNAM
 pwc1	 y		   x1			  0			0
PWLCON
 pwc1		  0			0
 pwc1		  5			5
 pwc1		  10		15