17.2 The MPS File Format

MOSEK supports the standard MPS format with some extensions. For a detailed description of the MPS format see the book by Nazareth [Naz87].

17.2.1 MPS File Structure

The version of the MPS format supported by MOSEK allows specification of an optimization problem of the form

(1)\[\begin{split}\begin{array} {rcccl} l^c & \leq & A x + q(x) & \leq & u^c, \\ l^x & \leq & x & \leq & u^x, \\ & & x \in \K, & & \\ & & x_{\mathcal{J}}\ \mbox{ integer}, & & \end{array}\end{split}\]

where

  • \(x \in \real^n\) is the vector of decision variables.
  • \(A \in \real^{m\times n}\) is the constraint matrix.
  • \(l^c \in \real^m\) is the lower limit on the activity for the constraints.
  • \(u^c \in \real^m\) is the upper limit on the activity for the constraints.
  • \(l^x \in \real^n\) is the lower limit on the activity for the variables.
  • \(u^x \in \real^n\) is the upper limit on the activity for the variables.
  • \(q: \real^n \rightarrow \real\) is a vector of quadratic functions. Hence,
\[q_i(x) = \half x^T Q^i x\]

where it is assumed that

\[Q^i = (Q^i)^T.\]

Please note the explicit \(\half\) in the quadratic term and that \(Q^i\) is required to be symmetric.

  • \(\K\) is a convex cone.
  • \(\mathcal{J} \subseteq \{1,2,\ldots ,n\}\) is an index set of the integer-constrained variables.

An MPS file with one row and one column can be illustrated like this:

*        1         2         3         4         5         6
*23456789012345678901234567890123456789012345678901234567890
NAME          [name]
OBJSENSE
[objsense]
OBJNAME
[objname]
ROWS
?  [cname1]
COLUMNS
[vname1]  [cname1]    [value1]     [vname3]  [value2]
RHS
[name]    [cname1]    [value1]     [cname2]  [value2]
RANGES
[name]    [cname1]    [value1]     [cname2]  [value2]
QSECTION      [cname1]
[vname1]  [vname2]    [value1]     [vname3]  [value2]
QMATRIX
[vname1]  [vname2]    [value1]
QUADOBJ
[vname1]  [vname2]    [value1]
QCMATRIX      [cname1]
[vname1]  [vname2]    [value1]
BOUNDS
?? [name]    [vname1]    [value1]
CSECTION      [kname1]    [value1]     [ktype]
[vname1]
ENDATA

Here the names in capitals are keywords of the MPS format and names in brackets are custom defined names or values. A couple of notes on the structure:

  • Fields: All items surrounded by brackets appear in fields. The fields named “valueN” are numerical values. Hence, they must have the format

      [+|-]XXXXXXX.XXXXXX[[e|E][+|-]XXX]
    
    
    where
    
    .. code-block:: text
    
       X = [0|1|2|3|4|5|6|7|8|9].
    
  • Sections: The MPS file consists of several sections where the names in capitals indicate the beginning of a new section. For example, COLUMNS denotes the beginning of the columns section.

  • Comments: Lines starting with an * are comment lines and are ignored by MOSEK.

  • Keys: The question marks represent keys to be specified later.

  • Extensions: The sections QSECTION and CSECTION are specific MOSEK extensions of the MPS format. The sections QMATRIX, QUADOBJ and QCMATRIX are included for sake of compatibility with other vendors extensions to the MPS format.

The standard MPS format is a fixed format, i.e. everything in the MPS file must be within certain fixed positions. MOSEK also supports a free format. See Section 17.2.9 for details.

Linear example lo1.mps

A concrete example of a MPS file is presented below:

* File: lo1.mps
NAME          lo1
OBJSENSE
    MAX
ROWS
 N  obj
 E  c1      
 G  c2      
 L  c3      
COLUMNS
    x1        obj       3
    x1        c1        3
    x1        c2        2
    x2        obj       1
    x2        c1        1
    x2        c2        1
    x2        c3        2
    x3        obj       5
    x3        c1        2
    x3        c2        3
    x4        obj       1
    x4        c2        1
    x4        c3        3
RHS
    rhs       c1        30
    rhs       c2        15
    rhs       c3        25
RANGES
BOUNDS
 UP bound     x2        10
ENDATA

Subsequently each individual section in the MPS format is discussed.

17.2.1.1 Section NAME

In this section a name ([name]) is assigned to the problem.

17.2.1.2 OBJSENSE (optional)

This is an optional section that can be used to specify the sense of the objective function. The OBJSENSE section contains one line at most which can be one of the following

MIN
MINIMIZE
MAX
MAXIMIZE

It should be obvious what the implication is of each of these four lines.

17.2.1.3 OBJNAME (optional)

This is an optional section that can be used to specify the name of the row that is used as objective function. The OBJNAME section contains one line at most which has the form

objname

objname should be a valid row name.

17.2.1.4 ROWS

A record in the ROWS section has the form

?  [cname1]

where the requirements for the fields are as follows:

Field Starting Position Max Width required Description
? 2 1 Yes Constraint key
[cname1] 5 8 Yes Constraint name

Hence, in this section each constraint is assigned an unique name denoted by [cname1]. Please note that [cname1] starts in position 5 and the field can be at most 8 characters wide. An initial key ? must be present to specify the type of the constraint. The key can have the values E, G, L, or N with the following interpretation:

Constraint type \(l_{i}^{c}\) \(u_i^c\)
E finite \(l_i^c\)
G finite \(\infty\)
L \(-\infty\) finite
N \(-\infty\) \(\infty\)

In the MPS format an objective vector is not specified explicitly, but one of the constraints having the key N will be used as the objective vector \(c\) . In general, if multiple N type constraints are specified, then the first will be used as the objective vector \(c\).

17.2.1.5 COLUMNS

In this section the elements of \(A\) are specified using one or more records having the form:

[vname1]  [cname1]    [value1]     [cname2]  [value2]

where the requirements for each field are as follows:

Field Starting Position Max Width required Description
[vname1] 5 8 Yes Variable name
[cname1] 15 8 Yes Constraint name
[value1] 25 12 Yes Numerical value
[cname2] 40 8 No Constraint name
[value2] 50 12 No Numerical value

Hence, a record specifies one or two elements \(a_{ij}\) of \(A\) using the principle that [vname1] and [cname1] determines \(j\) and \(i\) respectively. Please note that [cname1] must be a constraint name specified in the ROWS section. Finally, [value1] denotes the numerical value of \(a_{ij}\) . Another optional element is specified by [cname2], and [value2] for the variable specified by [vname1]. Some important comments are:

  • All elements belonging to one variable must be grouped together.
  • Zero elements of \(A\) should not be specified.
  • At least one element for each variable should be specified.

17.2.1.6 RHS (optional)

A record in this section has the format

[name]    [cname1]    [value1]     [cname2]  [value2]

where the requirements for each field are as follows:

Field Starting Position Max Width required Description
[name] 5 8 Yes Name of the RHS vector
[cname1] 15 8 Yes Constraint name
[value1] 25 12 Yes Numerical value
[cname2] 40 8 No Constraint name
[value2] 50 12 No Numerical value

The interpretation of a record is that [name] is the name of the RHS vector to be specified. In general, several vectors can be specified. [cname1] denotes a constraint name previously specified in the ROWS section. Now, assume that this name has been assigned to the \(i\) th constraint and \(v_1\) denotes the value specified by [value1], then the interpretation of \(v_1\) is:

Constraint \(l_i^c\) \(u_i^c\)
type    
E \(v_1\) \(v_1\)
G \(v_1\)  
L   \(v_1\)
N    

An optional second element is specified by [cname2] and [value2] and is interpreted in the same way. Please note that it is not necessary to specify zero elements, because elements are assumed to be zero.

17.2.1.7 RANGES (optional)

A record in this section has the form

[name]    [cname1]    [value1]     [cname2]  [value2]

where the requirements for each fields are as follows:

Field Starting Position Max Width required Description
[name] 5 8 Yes Name of the RANGE vector
[cname1] 15 8 Yes Constraint name
[value1] 25 12 Yes Numerical value
[cname2] 40 8 No Constraint name
[value2] 50 12 No Numerical value

The records in this section are used to modify the bound vectors for the constraints, i.e. the values in \(l^c\) and \(u^c\) . A record has the following interpretation:[name] is the name of the RANGE vector and [cname1] is a valid constraint name. Assume that [cname1] is assigned to the \(i\) th constraint and let \(v_1\) be the value specified by [value1], then a record has the interpretation:

Constraint type Sign of \(v_1\) \(l_i^c\) \(u_i^c\)
E \(-\) \(u_i^c+v_1\)  
E \(+\)   \(l_i^c+v_1\)
G \(-\) or \(+\) \(l_i^c+|v_1|\)  
L \(-\) or \(+\) \(u_i^c-|v_1|\)  
N      

17.2.1.8 QSECTION (optional)

Within the QSECTION the label [cname1] must be a constraint name previously specified in the ROWS section. The label [cname1] denotes the constraint to which the quadratic term belongs. A record in the QSECTION has the form

[vname1]  [vname2]    [value1]     [vname3]  [value2]

where the requirements for each field are:

Field Starting Position Max Width required Description
[vname1] 5 8 Yes Variable name
[vname2] 15 8 Yes Variable name
[value1] 25 12 Yes Numerical value
[vname3] 40 8 No Variable name
[value2] 50 12 No Numerical value

A record specifies one or two elements in the lower triangular part of the \(Q^i\) matrix where [cname1] specifies the \(i\) . Hence, if the names [vname1] and [vname2] have been assigned to the \(k\) th and \(j\) th variable, then \(Q_{kj}^i\) is assigned the value given by [value1] An optional second element is specified in the same way by the fields [vname1], [vname3], and [value2].

The example

\[\begin{split}\begin{array}{lccl} \mbox{minimize} & -x_2 + \frac{1}{2} ( 2 x_1^2 - 2 x_1 x_3 + 0.2 x_2^2 + 2 x_3^2 ) & & \\ \mbox{subject to} & x_1 + x_2 + x_3 & \geq & 1, \\ & x \geq 0 & & \end{array}\end{split}\]

has the following MPS file representation

* File: qo1.mps
NAME          qo1
ROWS
N  obj
G  c1
COLUMNS
x1        c1        1.0
x2        obj       -1.0
x2        c1        1.0
x3        c1        1.0
RHS
rhs       c1        1.0
QSECTION      obj
x1        x1        2.0
x1        x3        -1.0
x2        x2        0.2
x3        x3        2.0
ENDATA

Regarding the QSECTIONs please note that:

  • Only one QSECTION is allowed for each constraint.
  • The QSECTIONs can appear in an arbitrary order after the COLUMNS section.
  • All variable names occurring in the QSECTION must already be specified in the COLUMNS section.
  • All entries specified in a QSECTION are assumed to belong to the lower triangular part of the quadratic term of \(Q\) .

17.2.1.9 QMATRIX/QUADOBJ (optional)

The QMATRIX and QUADOBJ sections allow to define the quadratic term of the objective function. They differ in how the quadratic term of the objective function is stored:

  • QMATRIX It stores all the nonzeros coefficients, withouot taking advantage of the symmetry of the \(Q\) matrix.
  • QUADOBJ It only store the upper diagonal nonzero elements of the \(Q\) matrix.

A record in both sections has the form:

[vname1]  [vname2]    [value1]

where the requirements for each field are:

Field Starting Position Max Width required Description
[vname1] 5 8 Yes Variable name
[vname2] 15 8 Yes Variable name
[value1] 25 12 Yes Numerical value

A record specifies one elements of the \(Q\) matrix in the objective function . Hence, if the names [vname1] and [vname2] have been assigned to the \(k\) th and \(j\) th variable, then \(Q_{kj}\) is assigned the value given by [value1]. Note that a line must apper for each off-diagonal coefficient if using a QMATRIX section, while only one entry is required in a QUADOBJ section. The quadratic part of the objective function will be evaluated as \(1/2x^T Q x\).

The example

\[\begin{split}\begin{array}{lccl} \mbox{minimize} & -x_2 + \frac{1}{2} (2 x_1^2 - 2 x_1 x_3 + 0.2 x_2^2 + 2 x_3^2 ) & & \\ \mbox{subject to} & x_1+x_2+x_3 & \geq & 1, \\ & x \geq 0 & & \end{array}\end{split}\]

has the following MPS file representation using QMATRIX

* File: qo1_matrix.mps
NAME          qo1_qmatrix
ROWS
 N  obj
 G  c1
COLUMNS
    x1        c1        1.0
    x2        obj       -1.0
    x2        c1        1.0
    x3        c1        1.0
RHS
    rhs       c1        1.0
QMATRIX
    x1        x1        2.0
    x1        x3        -1.0
    x3        x1        -1.0
    x2        x2        0.2
    x3        x3        2.0
ENDATA

or the following using QUADOBJ

* File: qo1_quadobj.mps
NAME          qo1_quadobj
ROWS
 N  obj
 G  c1
COLUMNS
    x1        c1        1.0
    x2        obj       -1.0
    x2        c1        1.0
    x3        c1        1.0
RHS
    rhs       c1        1.0
QUADOBJ
    x1        x1        2.0
    x1        x3        -1.0
    x2        x2        0.2
    x3        x3        2.0
ENDATA

Please also note that:

  • A QMATRIX/QUADOBJ section can appear in an arbitrary order after the COLUMNS section.
  • All variable names occurring in the QMATRIX/QUADOBJ section must already be specified in the COLUMNS section.

17.2.2 QCMATRIX (optional)

A QCMATRIX section allows to specify the quadratic part of a given constraints. Within the QCMATRIX the label [cname1] must be a constraint name previously specified in the ROWS section. The label [cname1] denotes the constraint to which the quadratic term belongs. A record in the QSECTION has the form

[vname1]  [vname2]    [value1]

where the requirements for each field are:

Field Starting Position Max Width required Description
[vname1] 5 8 Yes Variable name
[vname2] 15 8 Yes Variable name
[value1] 25 12 Yes Numerical value

A record specifies an entry of the \(Q^i\) matrix where [cname1] specifies the \(i\). Hence, if the names [vname1] and [vname2] have been assigned to the \(k\) th and \(j\) th variable, then \(Q_{kj}^i\) is assigned the value given by [value1]. Moreover, the quadratic term is represented as \(1/2 x^T Q x\).

The example

\[\begin{split}\begin{array}{lccl} \mbox{minimize} & x_2 & & \\ \mbox{subject to} & x_1+x_2+x_3 & \geq & 1, \\ & \frac{1}{2} ( - 2 x_1 x_3 + 0.2 x_2^2 + 2 x_3^2 )& \leq & 10,\\ & x \geq 0 & & \end{array}\end{split}\]

has the following MPS file representation

* File: qo1.mps
NAME          qo1
ROWS
 N  obj
 G  c1
 L  q1
COLUMNS
    x1        c1        1.0
    x2        obj       -1.0
    x2        c1        1.0
    x3        c1        1.0
RHS
    rhs       c1        1.0
    rhs       q1        10.0
QCMATRIX      q1
    x1        x1        2.0
    x1        x3        -1.0
    x3        x1        -1.0
    x2        x2        0.2
    x3        x3        2.0
ENDATA

Regarding the QCMATRIXs please note that:

  • Only one QCMATRIX is allowed for each constraint.
  • The QCMATRIXs can appear in an arbitrary order after the COLUMNS section.
  • All variable names occurring in the QSECTION must already be specified in the COLUMNS section.
  • A QCMATRIX does not exploit the symmetry of \(Q\): an off-diagonal entry \((i,j)\) should apperas twice.

17.2.3 BOUNDS (optional)

In the BOUNDS section changes to the default bounds vectors \(l^x\) and \(u^x\) are specified. The default bounds vectors are \(l^x = 0\) and \(u^x = \infty\) . Moreover, it is possible to specify several sets of bound vectors. A record in this section has the form

?? [name]    [vname1]    [value1]

where the requirements for each field are:

Field Starting Position Max Width Required Description
?? 2 2 Yes Bound key
[name] 5 8 Yes Name of the BOUNDS vector
[vname1] 15 8 Yes Variable name
[value1] 25 12 No Numerical value

Hence, a record in the BOUNDS section has the following interpretation:[name] is the name of the bound vector and [vname1] is the name of the variable which bounds are modified by the record. ?? and [value1] are used to modify the bound vectors according to the following table:

?? \(l_j^x\) \(u_j^x\) Made integer (added to \(\mathcal{J}\) )
FR \(-\infty\) \(\infty\) No
FX \(v_1\) \(v_1\) No
LO \(v_1\) unchanged No
MI \(-\infty\) unchanged No
PL unchanged \(\infty\) No
UP unchanged \(v_1\) No
BV \(0\) 1 Yes
LI \(\lceil v_1 \rceil\) unchanged Yes
UI unchanged \(\lfloor v_1 \rfloor\) Yes

v_1 is the value specified by [value1].

17.2.4 CSECTION (optional)

The purpose of the CSECTION is to specify the constraint

\[x \in \K.\]

in (1). It is assumed that \(\K\) satisfies the following requirements. Let

\[x^t \in \real^{n^t}, \quad t=1,\ldots ,k\]

be vectors comprised of parts of the decision variables \(x\) so that each decision variable is a member of exactly one vector \(x^t\), for example

\[\begin{split}x^1 = \left[ \begin{array} {c} x_1 \\ x_4 \\ x_7 \end{array} \right] \quad \mbox{ and }\quad x^2 = \left[ \begin{array} {c} x_6 \\ x_5 \\ x_3 \\ x_2 \end{array} \right].\end{split}\]

Next define

\[\K := \left\lbrace x \in \real^n: \quad x^t \in \K_t,\quad t=1,\ldots ,k \right\rbrace\]

where \(\K_t\) must have one of the following forms

  • \(\real\) set:

    \[\K_t = \left\{ x \in \real^{n^t} \right\}.\]
  • Quadratic cone:

    (2)\[\K_t = \left\lbrace x \in \real^{n^t}: x_1 \geq \sqrt{\sum_{j=2}^{n^t} x_j^2} \right\rbrace.\]
  • Rotated quadratic cone:

    (3)\[\K_t = \left\lbrace x \in \real^{n^t}: 2 x_1 x_2 \geq \sum_{j=3}^{n^t} x_j^2,\quad x_1,x_2 \geq 0 \right\rbrace.\]

In general, only quadratic and rotated quadratic cones are specified in the MPS file whereas membership of the \(\real\) set is not. If a variable is not a member of any other cone then it is assumed to be a member of an \(\real\) cone.

Next, let us study an example. Assume that the quadratic cone

\[x_4 \geq \sqrt{x_5^2 + x_8^2}\]

and the rotated quadratic cone

\[x_3 x_7 \geq x_1^2 + x_0^2, \quad x_3,x_7 \geq 0,\]

should be specified in the MPS file. One CSECTION is required for each cone and they are specified as follows:

*        1         2         3         4         5         6
*23456789012345678901234567890123456789012345678901234567890
CSECTION      konea       0.0          QUAD
x4
x5
x8
CSECTION      koneb       0.0          RQUAD
x7
x3
x1
x0

This first CSECTION specifies the cone (2) which is given the name konea. This is a quadratic cone which is specified by the keyword QUAD in the CSECTION header. The 0.0 value in the CSECTION header is not used by the QUAD cone.

The second CSECTION specifies the rotated quadratic cone (3). Please note the keyword RQUAD in the CSECTION which is used to specify that the cone is a rotated quadratic cone instead of a quadratic cone. The 0.0 value in the CSECTION header is not used by the RQUAD cone.

In general, a CSECTION header has the format

CSECTION      [kname1]    [value1]     [ktype]

where the requirement for each field are as follows:

Field Starting Position Max Width Required Description
[kname1] 5 8 Yes Name of the cone
[value1] 15 12 No Cone parameter
[ktype] 25   Yes Type of the cone.

The possible cone type keys are:

Cone type key Members Interpretation.
QUAD \(\leq 1\) Quadratic cone i.e. (2).
RQUAD \(\leq 2\) Rotated quadratic cone i.e. (3).

Please note that a quadratic cone must have at least one member whereas a rotated quadratic cone must have at least two members. A record in the CSECTION has the format

[vname1]

where the requirements for each field are

Field Starting Position Max Width required Description
[vname1] 2 8 Yes A valid variable name

The most important restriction with respect to the CSECTION is that a variable must occur in only one CSECTION.

17.2.5 ENDATA

This keyword denotes the end of the MPS file.

17.2.6 Integer Variables

Using special bound keys in the BOUNDS section it is possible to specify that some or all of the variables should be integer-constrained i.e. be members of \(\mathcal{J}\) . However, an alternative method is available.

This method is available only for backward compatibility and we recommend that it is not used. This method requires that markers are placed in the COLUMNS section as in the example:

COLUMNS
x1        obj       -10.0          c1        0.7
x1        c2        0.5            c3        1.0
x1        c4        0.1
* Start of integer-constrained variables.
MARK000   'MARKER'                 'INTORG'
x2        obj       -9.0           c1        1.0
x2        c2        0.8333333333   c3        0.66666667
x2        c4        0.25
x3        obj       1.0            c6        2.0
MARK001   'MARKER'                 'INTEND'
  • End of integer-constrained variables.

Please note that special marker lines are used to indicate the start and the end of the integer variables. Furthermore be aware of the following

  • IMPORTANT: All variables between the markers are assigned a default lower bound of 0 and a default upper bound of 1. This may not be what is intended. If it is not intended, the correct bounds should be defined in the BOUNDS section of the MPS formatted file.
  • MOSEK ignores field 1, i.e. MARK0001 and MARK001, however, other optimization systems require them.
  • Field 2, i.e. MARKER, must be specified including the single quotes. This implies that no row can be assigned the name MARKER.
  • Field 3 is ignored and should be left blank.
  • Field 4, i.e. INTORG and INTEND, must be specified.
  • It is possible to specify several such integer marker sections within the COLUMNS section.

17.2.7 General Limitations

  • An MPS file should be an ASCII file.

17.2.8 Interpretation of the MPS Format

Several issues related to the MPS format are not well-defined by the industry standard. However, MOSEK uses the following interpretation:

  • If a matrix element in the COLUMNS section is specified multiple times, then the multiple entries are added together.
  • If a matrix element in a QSECTION section is specified multiple times, then the multiple entries are added together.

17.2.9 The Free MPS Format

MOSEK supports a free format variation of the MPS format. The free format is similar to the MPS file format but less restrictive, e.g. it allows longer names. However, it also presents two main limitations:

  • A name must not contain any blanks.
  • By default a line in the MPS file must not contain more than 1024 characters. However, by modifying the parameter MSK_IPAR_READ_MPS_WIDTH an arbitrary large line width will be accepted.

To use the free MPS format instead of the default MPS format the MOSEK parameter MSK_IPAR_READ_MPS_FORMAT should be changed.