.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:
NAME Section
OBJSENSE Section (Optional)
ROWS Section
COLUMNS Section - Integrality Markers (Optional)
RHS Section
BOUNDS Section (Optional)
SOS Section (Optional)
QUADOBJ Section (Optional)
QCMATRIX Section (Optional)
INDICATOR Constraints (Optional)
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#
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.
Comments#
Lines starting with an asterisk * are treated as comments and are ignored by the parser.