.mps format for MIPs#

Introduction#

The MPS (Mathematical Programming System) format is one of the oldest and most widely used formats for representing optimization models. Originally developed for linear programming, it has been extended to support more complex models, including mixed-integer and quadratic programming. The format is designed to be machine-readable, and while it may be less intuitive than formats like LP, it remains a standard in the field due to its wide adoption. All files that correspond to this format must have the extension .mps in the file name.

Basic Structure#

An MPS file is divided into several sections, each serving a specific purpose in defining the optimization model. The general structure includes:

  1. NAME Section

  2. OBJSENSE Section (Optional)

  3. ROWS Section

  4. COLUMNS Section - Integrality Markers (Optional)

  5. RHS Section

  6. BOUNDS Section (Optional)

  7. SOS Section (Optional)

  8. QUADOBJ Section (Optional)

  9. QCMATRIX Section (Optional)

  10. INDICATOR Constraints (Optional)

  11. ENDATA Statement

Please note that the order of these sections must be adhered to in order to guarantee a correct processing of the problem!

Fixed Format vs. Free Format#

MPS files can be written in either fixed or free format:

  • Fixed Format: Fields start at specific columns in each line.

  • Free Format: Fields are separated by whitespace and can be of variable length.

Key Differences:

  • In fixed format, names (rows, columns) are limited to 8 characters and can include spaces.

  • In free format, names can be longer (up to 255 characters in most implementations) but cannot contain spaces.

Most modern solvers including the Quantagonia HybridSolver can automatically detect the format used. Naturally, the fixed format is always a valid free format, therefore we mainly present examples in fixed format below.

1. NAME Section#

The NAME section identifies the problem name.

Fixed Format Example:

NAME          SAMPLE
  • Position: The problem name starts at column 15.

2. OBJSENSE Section (Optional)#

Specifies the optimization direction (minimize or maximize). By default, the objective is minimized.

Example:

OBJSENSE
  MAX

Place this section after the NAME section if you want to maximize the objective function.

3. ROWS Section#

Defines the rows of the model, which correspond to constraints and the objective function.

Structure:

  • Type Indicator: Indicates the type of the row.

    • E: Equality (=).

    • L: Less-than-or-equal (<=).

    • G: Greater-than-or-equal (>=).

    • N: Free row (often used for the objective function).

  • Row Name: The identifier for the constraint or objective.

Fixed Format Example:

ROWS
 E  EQ1
 L  LEQ1
 G  GEQ1
 N  OBJ
  • Positions:

    • Type Indicator: Column 2.

    • Row Name: Starts at column 5.

Note: The first N row encountered is typically treated as the objective function.

4. COLUMNS Section#

Lists the variables (columns) and their coefficients in the constraints and objective function.

Structure:

  • Column Name: The variable’s identifier.

  • Row Name and Coefficient: Specifies the coefficient of the variable in a particular row (constraint or objective).

Each line can contain up to two (row, coefficient) pairs for the variable.

Fixed Format Example:

COLUMNS
    X1        EQ1        1.0     OBJ        3.0
    X1        LEQ1       2.0
    X2        EQ1        1.0     OBJ        4.0
    X2        GEQ1       3.0
  • Positions:

    • Column Name: Starts at column 5.

    • First Row Name: Starts at column 15.

    • First Coefficient: Starts at column 25.

    • Second Row Name: Starts at column 40.

    • Second Coefficient: Starts at column 50.

Important Notes:

  • All entries for a variable should be contiguous.

  • Coefficients for the objective function are associated with the row name used for the objective (usually the first N row).

Integrality Markers (Optional)#

Used to indicate that variables between markers are integer variables. By default, all variables within markers have a lower bound of 0 and an upper bound of 1. Other bounds can be specified in the BOUNDS section.

Markers:

  • Start Marker: ‘MARKER’ ‘INTORG’

  • End Marker: ‘MARKER’ ‘INTEND’

Example:

MARK0000 'MARKER'                 'INTORG'
X1        EQ1        1.0     OBJ        3.0
X2        EQ1        1.0     OBJ        4.0
MARK0000 'MARKER'                 'INTEND'
  • Variables X1 and X2 are declared as integer variables.

  • Positions:

    • Marker Name: Starts at column 5.

    • Marker Keyword: Starts at column 15 and must be equal to ‘MARKER’ including the quotes.

    • Integer Section Keyword: Starts at column 40 and must be equal to ‘INTORG’ at the start and ‘INTEND’ at the end of the integer section, again including the quotes.

5. RHS Section#

Specifies the right-hand side values for the constraints.

Structure:

  • RHS Name: Generally ignored by modern solvers.

  • Row Name and Value: Specifies the right-hand side value for a constraint.

Each line can contain up to two (row, value) pairs.

Fixed Format Example:

RHS
    RHS1      EQ1        5.0     LEQ1      10.0
    RHS1      GEQ1       2.0
  • Positions:

    • RHS Name: Starts at column 5.

    • First Row Name: Starts at column 15.

    • First Value: Starts at column 25.

    • Second Row Name: Starts at column 40.

    • Second Value: Starts at column 50.

Note: Rows not mentioned in the RHS section have a right-hand side value of zero.

6. BOUNDS Section (Optional)#

Defines the bounds on variables. By default, variables have a lower bound of zero and no upper bound.

Bound Types:

  • LO: Lower bound.

  • UP: Upper bound.

  • FX: Fixed variable (both bounds equal).

  • FR: Free variable (no bounds).

  • MI: Minus infinity (no lower bound).

  • PL: Plus infinity (no upper bound).

  • BV: Binary variable (0 or 1).

  • LI: Integer variable lower bound.

  • UI: Integer variable upper bound.

  • SC: Semi-continuous variable upper bound.

  • SI: Semi-integer variable upper bound.

Structure:

  • Bound Type

  • Bound Name: Generally ignored.

  • Variable Name

  • Value: The bound value (if applicable).

Fixed Format Example:

BOUNDS
 UP BND       X1         10.0
 LO BND       X2          1.0
 FX BND       X3          5.0
 FR BND       X4
 BV BND       X5
  • Positions:

    • Bound Type: Column 2.

    • Bound Name: Starts at column 5.

    • Variable Name: Starts at column 15.

    • Value: Starts at column 25.

7. SOS Section (Optional)#

Defines Special Ordered Sets (SOS) constraints of type 1 and 2.

SOS Types:

  • S1: SOS Type 1

  • S2: SOS Type 2

Structure:

  • SOS Type

  • SOS Name

  • Variable and Weight: Each member variable and its weight.

Fixed Format Example:

SOS
 S1 SOS1
    X1           1
    X2           2
 S2 SOS2
    X3           1
    X4           2
    X5           3
  • Positions:

    • SOS Type (S1 or S2): Column 2.

    • SOS Name: Starts at column 5.

    • Variable Name: Starts at column 5.

    • Weight: Starts at column 15.

8. QUADOBJ Section (Optional)#

Defines quadratic terms in the objective function.

Structure:

  • Variable 1

  • Variable 2

  • Coefficient

Only the lower triangle (or full symmetric entries) needs to be specified due to symmetry.

Fixed Format Example:

QUADOBJ
    X1        X1         2.0
    X1        X2         1.0
    X2        X2         3.0
  • Represents the quadratic objective: \(\frac{1}{2}(2X1^2 + 2X1 \cdot X2 + 3X2^2)\).

  • Positions:

    • QUADOBJ: Starts at column 1.

    • Variable 1: Starts at column 5.

    • Variable 2: Starts at column 15.

    • Coefficient: Starts at column 25.

9. QCMATRIX Section (Optional)#

Defines quadratic terms in quadratic constraints.

Structure:

  • QCMATRIX: Followed by the constraint name.

  • Variable 1

  • Variable 2

  • Coefficient

Fixed Format Example:

QCMATRIX    QC1
    X1        X1         1.0
    X1        X2         0.5
    X2        X2         1.5
  • Quadratic terms for constraint QC1.

  • Positions:

    • QCMATRIX: Starts at column 1.

    • Constraint Name: Starts at column 12.

    • Variable 1: Starts at column 5.

    • Variable 2: Starts at column 15.

    • Coefficient: Starts at column 25.

10. INDICATOR Constraints (Optional)#

Defines indicator constraints, which activate constraints based on the value of a binary variable.

Structure:

  • IF

  • Row Name

  • Binary Variable

  • Value: 0 or 1

Fixed Format Example:

INDICATORS
 IF  CONSTR1  BIN_VAR1   1
 IF  CONSTR2  BIN_VAR2   0
  • Constraint CONSTR1 is activated when BIN_VAR1 = 1.

  • Positions:

    • INDICATORS: Starts at column 1 (header line).

    • IF: Column 2.

    • Row Name: Starts at column 5 (Keep in mind that the row must have already been defined in the ROWS section!).

    • Binary Variable: Starts at column 15.

    • Value: Starts at column 25.

11. ENDATA Statement#

Marks the end of the MPS file.

Example:

ENDATA

Examples of MPS Models#

Below are examples of MPS files representing different types of optimization problems.

Example 1: Linear Programming (LP) Problem#

NAME          SIMPLELP
ROWS
 N  COST
 L  CONSTR1
 G  CONSTR2
COLUMNS
    X1        CONSTR1    1.0     COST       3.0
    X1        CONSTR2   -1.0
    X2        CONSTR1    2.0     COST       5.0
    X2        CONSTR2    1.0
RHS
    RHS1      CONSTR1   10.0     CONSTR2    5.0
BOUNDS
 LO BND       X1         0.0
 LO BND       X2         0.0
ENDATA

Explanation:

  • Objective: Minimize the cost function \(3X1 + 5X2\).

  • Constraints:

    • CONSTR1: \(X1 + 2X2 \leq 10\).

    • CONSTR2: \(-X1 + X2 \geq 5\).

  • Bounds: \(X1, X2 \geq 0\).

Example 2: Mixed-Integer Programming (MIP) Problem#

NAME          SIMPLEMIP
ROWS
 N  PROFIT
 L  LIMIT1
 L  LIMIT2
COLUMNS
    MARK0000 'MARKER'                 'INTORG'
    X1        LIMIT1     1.0      PROFIT     10.0
    X1        LIMIT2     1.0
    X2        LIMIT1     1.0      PROFIT      6.0
    X2        LIMIT2     2.0
    X3        LIMIT1     1.0      PROFIT      4.0
    X3        LIMIT2     3.0
    MARK0000 'MARKER'                 'INTEND'
RHS
    RHS1      LIMIT1   100.0     LIMIT2    200.0
BOUNDS
 LO BND       X1         0.0
 LO BND       X2         0.0
 LO BND       X3         0.0
ENDATA

Explanation:

  • Objective: Maximize profit \(10X1 + 6X2 + 4X3\).

  • Constraints:

    • LIMIT1: \(X1 + X2 + X3 \leq 100\).

    • LIMIT2: \(X1 + 2X2 + 3X3 \leq 200\).

  • Variable Types: X1, X2, X3 are integer variables (between INTORG and INTEND markers).

  • Bounds: \(X1, X2, X3 \geq 0\).

Example 3: Quadratic Programming (QP) Problem#

NAME          SIMPLEQP
ROWS
 N  OBJ
 E  QC1
COLUMNS
    X1        QC1        1.0     OBJ        0.0
    X2        QC1        1.0     OBJ        0.0
RHS
    RHS1      QC1        1.0
BOUNDS
 LO BND       X1         0.0
 LO BND       X2         0.0
QUADOBJ
    X1        X1         1.0
    X2        X2         1.0
    X1        X2         0.0
ENDATA

Explanation:

  • Objective: Minimize \(\frac{1}{2}(X1^2 + X2^2)\).

  • Constraint: QC1: \(X1 + X2 = 1\).

  • Bounds: \(X1, X2 \geq 0\).

Additional Notes#

Comments#

  • Lines starting with an asterisk * are treated as comments and are ignored by the parser.

Fixed Format vs. Free Format#

  • In Fixed Format, fields start at specific columns in each line. Names are limited to 8 characters and can include spaces.

  • In Free Format, fields are separated by whitespace. Names can be longer (up to 255 characters) but cannot contain spaces.

Ordering#

  • Sections should appear in the order specified for the file to be correctly interpreted.

Precision#

  • Be cautious of potential precision loss due to fixed formats; consider using free format or solvers that support full precision.

Consistency#

  • Ensure consistent use of variable and constraint names throughout the file.

Objective Function#

  • The objective function is typically associated with the first N row in the ROWS section.

Case Sensitivity#

  • The MPS format is case-insensitive, but it’s good practice to be consistent.

Conclusion#

The MPS format is a powerful and widely accepted standard for representing optimization models. By understanding its structure and conventions, you can effectively model and solve a wide range of optimization problems using various solvers that support this format.