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. |
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
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
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. The defined matrices must be positive semi-definite. QCMATRICES must be defined only for rows of type L or G and must have no range value defined in the RANGE section..
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.
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.
ENDATA section
| Format: | Cols 1-6 |
|---|---|
| ENDATA |
is the last record of the file.