9.1. Model Files¶

File Type	Description	Format Type	Purpose
MPS QPS REW DUA	Ordinary MPS format file MPS format file, but implying it is a QP problem MPS format file, but its variables and constraints have been renamed MPS format file, but it writes out the dual problem	MPS	Compact, efficient storage of models
LP ILP RLP DLP	Ordinary LP format file LP format file, but it writes out the relaxed model after computing IIS LP format file, but its variables and constraints have been renamed LP format file, but it writes out the dual problem	LP	Easy for humans to read and check

It can be seen that the same format type contains multiple file types. For example, MPS format has four file types.

When MindOpt reads models, there is no difference between file types under the same format type. However, when MindOpt writes files, different file types will write different models to the file.

That is to say, when writing files, file type corresponds to data content, while format type corresponds to data format.

9.1.1. MPS File Format¶

MPS format is the most popular model storage format in the industry. Compared to LP file format, it has the following advantages:

More compact storage. For the same problem, an MPS is usually smaller than an LP file.

Higher tolerance and fewer restrictions for variable or constraint names.

Parser-friendly: Due to its positional field structure, MPS can be parsed more efficiently than LP, which relies on contextual keywords.

Stronger expressiveness. Although the LP format later enhanced its expressiveness through non-standard extensions to approach MPS in certain aspects, MPS remains the more general standard.

MPS has two forms: fixed format and free format. Fixed format requires that fields in the file must start at fixed positions and end at fixed positions. It can be seen that this limits the length of fields, such as an entity name being allowed a maximum of 8 characters. Clearly, fixed format is very traditional, while free format is more modern. Fixed format looks more elegant, while free format has stronger expressiveness.

Generally speaking, free format is compatible with fixed format, and MindOpt reads and outputs models in free format.

Note

Although variable and constraint names in standard fixed format can have 8 characters and can contain spaces, MindOpt does not support names containing spaces.

Let us first observe a simple MPS file.

* mps example
NAME          foo     FREE
OBJSENSE
    MAX
ROWS
 N  OBJ
 L  R0
 L  R1
 L  R2
COLUMNS
    C0 OBJ 1 R0 10
    C0 R1 1 R2 1
    C1 OBJ 3 R0 1
    C1 R1 10 R2 1
RHS
    RHS R0 10 R1 10
    RHS R2 1.5
ENDATA

Through observation, we find:

Lines starting with * seem to be comments. In fact, only when * appears at the beginning of a line will it be treated as a comment.

From the line indentation, it seems that an MPS consists of multiple “sections”. In fact, only section names, ENDATA, and * can appear at the beginning of a line without indentation, other content must belong to “sections”. Lines within a “section” must have indentation, but the number of indentation spaces is unlimited.

In MPS files, there are some that look like reserved words (such as MAX), some like names (such as C0), and some are numerical values.

ENDATA indicates the end of the file.

Since MPS parses field meanings based on their positions (while LP parsing relies on context to some extent), it has almost no restrictions on variable names and constraint names except that they cannot contain spaces.

An MPS file ends with ENDATA, and it may contain some or all of the following sections:

Section Name	Appearance Order	Required	Description
NAME	1	Yes	Model Name
OBJSENSE	2	Yes	Optimization Direction
ROWS	3	Yes	Constraint List and Inequality Direction
COLUMNS	4	Yes	Variables and Their Associated Constraint List
RHS	After ROWS		Right-hand Side Values of Constraints
RANGES	After ROWS		Constraint Range Length
BOUNDS	After COLUMNS		Variable Bounds
QUADOBJ	After COLUMNS		Quadratic Objective Matrix (Upper Triangular)
QMATRIX	After COLUMNS		Quadratic Objective Matrix
QCMATRIX	After COLUMNS		Quadratic Constraints
SOS	After COLUMNS		SOS Constraints
INDICATORS	After COLUMNS		Indicator Constraints

9.1.1.1. NAME section¶

NAME          foo     FREE

The NAME section records the model name and the model output format. MindOpt ignores the model format and treats everything as free format.

9.1.1.2. OBJSENSE section¶

OBJSENSE
    MAX

The OBJSENSE section records the model’s optimization direction. The two optional reserved words are:

MAX: Optimization direction for maximizing the objective function

MIN: Optimization direction for minimizing the objective function

9.1.1.3. ROWS section¶

ROWS
 N  OBJ
 L  R0
 L  R1
 L  R2

The ROWS section lists all constraint names and their inequality directions. Specifically, the first constraint with inequality direction N will be treated as the objective function.

The above example describes 3 constraints and one objective function. The inequality symbols of these 3 constraints are all \(\le\). The following table lists all possible inequality directions.

Reserved Word	Inequality Symbol
L	Less than or equal to
G	Greater than or equal to
E	Equal to
N	Objective function name

If the model is a single-objective model, only the first name marked with N will be treated as the objective function. However, if the model is a multi-objective optimization model, there can be multiple N markers. For example:

N  OBJ0 0 1 1e-06 0
N  OBJ1 -1 1 0.2 0

describes two objectives, OBJ0 and OBJ1. The 4 values appearing after the objective names correspond to ObjNPriority, ObjNWeight, ObjNAbsTol and ObjNRelTol. For multi-objective optimization, please refer to Multi-Objective Optimization.

9.1.1.4. COLUMNS section¶

COLUMNS
    C0 OBJ 1 R0 10
    C0 R1 1 R2 1
    C1 OBJ 3 R0 1
    C1 R1 10 R2 1

The COLUMNS section describes the objective function expression (excluding constant terms) and the constraint matrix.

Except for the objective function being special, the COLUMNS section actually describes a Compressed sparse column structure. Each of its lines starts with a variable name and can contain one or two Terms.

In the above example, the COLUMNS section describes two variables and their coefficients in three constraints, totaling 6 terms.

\[\begin{split}R0: 10 \times C0 + 1 \times C1 \\ R1: 1 \times C0 + 10 \times C1 \\ R2: 1 \times C0 + 1 \times C1\end{split}\]

The objective function is: \(1 \times C0 + 3 \times C1\)

Note

A line in the COLUMNS section can only contain one or two terms.

Note

Multiple lines starting with the same variable in the COLUMNS section must be adjacent.

9.1.1.5. RHS section¶

RHS
    RHS R0 10 R1 10
    RHS R2 1.5

The RHS section describes the right-hand side values of constraints.

Each line starts with a name, which MindOpt ignores. This is followed by descriptions of the right-hand side values of constraints. As in the above example, it describes the right-hand side values of three constraints.

Specifically, in the RHS section, the right-hand side value corresponding to the objective function name is the opposite number of the objective function constant term. Intuitively, we can understand this as:

\[\begin{split}\begin{align} OBJ: &\sum_{i}x_{i} &\quad ineq &\quad RHS \\ => &\sum_{i}x_{i} - RHS &\quad ineq &\quad 0 \end{align}\end{split}\]

Note

Each line can only contain one or two right-hand side value descriptions.

Note

If a constraint appearing in the ROWS section does not appear here, its right-hand side value defaults to 0.

9.1.1.6. RANGES section¶

RANGES
    RANGE0 R0 10 R1 10

The RANGES section follows the same format syntax as the RHS section, i.e., first a name that will be ignored by MindOpt, followed by one or two descriptions of constraint range lengths. As a supplement to the RHS section, it provides left-hand side values for constraints by describing constraint range lengths. For example: There is a constraint R0

In the ROWS section, the inequality symbol of R0 is \(\le\)

In the RHS section, the right-hand side value of R0 is 5

In the RANGES section, the range length of R0 is 9

Then the bounds of constraint R0 are:

\[-4 \le R0 \le 5\]

Assuming the current lower bound of the constraint is \(l\), and its upper bound is \(u\), in the RANGES section, the constraint has a value of \(v\), then the upper and lower bounds of the constraint will be updated according to the following table.

Constraint Inequality	Sign of \(v\)	Constraint Lower Bound (\(l\))	Constraint Upper Bound (\(u\))
E	\(-\)	\(u + v\)
E	\(+\)		\(l + v\)
G	\(+/-\)		\(u + \|v\|\)
L	\(+/-\)	\(u - \|v\|\)

Note

Like the RHS section, each line can only contain one or two range length value descriptions.

9.1.1.7. BOUNDS section¶

The BOUNDS section describes the upper and lower bounds of variables in the model. The default bounds for variables are \([0, \infty)\). The values provided in the BOUNDS section are used to update the upper and lower bounds of variables. For example:

BOUNDS
 UP BND1      x0  1
 UP BND1      x1  1
 UP BND1      x2  1

A line in the BOUNDS section consists of a bound descriptor, a name that will be ignored by MindOpt, a variable name, and a value. As in the above example, it describes 3 continuous variables x0, x1 and x2, all with upper bounds of 1.

Bound descriptors are a set of agreed reserved words that specify how to use the value to update variables and whether to change the variable type (whether to convert to integer variables). Assuming the current value is \(v\), all possible bound descriptors and corresponding rules are shown in the following table.

Bound Descriptor	Lower Bound	Upper Bound	Change Variable Type
FR	\(-\infty\)	\(\infty\)
FX	\(v\)	\(v\)
LO	\(v\)
MI	\(-\infty\)
PL		\(\infty\)
UP		\(v\)
BV	0	1	Convert to integer
LI	\(v\)		Convert to integer
UI		\(v\)	Convert to integer

Note

From the above table, FR, MI and PL do not require the \(v\) value. When the bound descriptor is one of these three, a line can have only 3 fields, and any subsequent fields will be ignored by MindOpt.

Note

The same variable can be described multiple times. When there are multiple lines describing a variable, reordering these lines may affect the final result.

9.1.1.8. QUADOBJ section¶

The QUADOBJ section describes the quadratic objective in the model. It records the coefficient matrix of the quadratic objective (commonly called the \(Q\) matrix) in Coordinate matrix format. Since the coefficient matrix of the quadratic objective is symmetric (and often positive definite), the QUADOBJ section only records its upper triangular part.

In the standard form of quadratic programming, the objective function is as follows:

\[\frac{1}{2}x^T Q x + C^T x\]

We assume the model has two variables, x and y, and we have the following description:

QUADOBJ
 x        x        2.0
 x        y        -1.0

After symmetric matrix replication of the upper triangle, the \(Q\) matrix in the standard form is:

\[\begin{split}\begin{bmatrix} 2 & -1 \\ -1 & 0 \end{bmatrix}\end{split}\]

Since the standard form has a coefficient \(\frac{1}{2}\), the actual modeling expression for the objective function is:

\[x^2 - \frac{1}{2} xy - \frac{1}{2} yx\]

That is

\[x^2 - xy\]

9.1.1.9. QMATRIX section¶

The QMATRIX section is almost identical to the QUADOBJ section. The only difference is that it records the complete \(Q\) matrix instead of just the upper triangular part. Obviously, the existence of the QMATRIX section is only for compatibility. The QUADOBJ section is more efficient and compact.

Note

A MPS file should not contain both QUADOBJ section and QMATRIX section.

9.1.1.10. QCMATRIX section¶

The QCMATRIX section can have multiple instances, each QCMATRIX section describing the coefficient matrix in a quadratic constraint. For example:

QCMATRIX qc1
 x        x        2.0
 x        y        -1.0
 y        x        -1.0

It can be observed that each QCMATRIX section must be associated with a known constraint (i.e., a constraint name that appears in the ROWS section), such as qc1 in this example. This is followed by the quadratic term coefficient matrix in that constraint. Like the QMATRIX section and unlike the QUADOBJ section, QCMATRIX does not utilize symmetry and fully records the coefficient matrix of the quadratic constraint terms.

Please note that unlike the QUADOBJ section, QCMATRIX often records coefficients directly, so the modeling expression for this constraint is:

\[2x^2 - 2xy\]

9.1.1.11. SOS section¶

The SOS section describes the SOS constraints in the model.

SOS
 S2 sos1
    x1           1
    x2           2
 S1 sos2
    x2           2
    x3           3

It can be observed that there are different levels of indentation in the SOS section. In fact, the SOS section is divided into multiple subsections, each subsection describing one SOS constraint.

Such as the first subsection

S2 sos1
   x1          1
   x2          2

In the first line, S2 indicates that this constraint is an SOS2 constraint (another possible value is S1, indicating an SOS1 constraint), and the constraint name is sos1.

Reserved Word	SOS Constraint Type	Meaning
S1	Special Ordered Set of Type 1	At most one variable can take a non-zero value
S2	Special Ordered Set of Type 2	After sorting by weights, at most two adjacent variables can take non-zero values

The following lines list the variables in the SOS constraint and the weights corresponding to the variables.

9.1.1.12. INDICATORS section¶

The INDICATORS section describes the indicator constraints in the model.

INDICATORS
 IF row1      x        0
 IF row2      y        1

Each line in the INDICATORS section describes an indicator constraint. For example

IF R0      x        0

describes the indicator constraint: when variable x takes the value 0, constraint R0 is activated. Where:

R0 must be a constraint name appearing in the ROWS section, and must be a linear constraint

x must be a variable name appearing in the COLUMNS section

The last field must be 0 or 1

9.1.2. QPS File¶

It can be simply understood that QPS is an alias for MPS, and they have no difference whatsoever.

We conventionally (but not necessarily) store QP or QCP problems (i.e., containing one or more of sections QUADOBJ, QMATRIX, QCMATRIX) in a .qps file. But this does not mean that all QP and QCP problems must use .qps as the extension when writing files.

It can be understood that: the significance of QPS files exists merely to define a naming convention.

9.1.3. REW File¶

This is an MPS format file written after renaming variables and constraints.

It has two main typical uses:

Data anonymization. The business meaning of data may be implied in variable or constraint names. Renaming to meaningless names can hide sensitive information.

Filtering illegal names. When variables and constraints contain illegal characters, some solvers may not be able to read them. In this case, if an REW format file is written, almost all solvers can read it.

How does REW rename variables and constraints?

We assume a variable’s index is i, and n constraints reference this variable. When:

It is a continuous variable, it is named: C{i}({n}), such as C0(7)

It is a general integer variable, it is named: I{i}({n})

It is a binary variable, it is named: B{i}({n})

And assuming a constraint’s index is j, then its name is c{j}. It can be seen that a constraint’s name only relates to its index number, such as c7 indicating it is the 8th constraint.

9.1.4. DUA File¶

Writing a DUA file means writing the dual problem of the current problem as a REW file.

The variables of the dual problem correspond to the constraints of the original problem. And the constraints of the dual problem correspond to the variables of the original problem. However, in practice, it will be found that the written dual problem may not correspond to the original problem in terms of rows and columns.

In fact, we only guarantee that if the original problem has N constraints, then the first N variables in the DUA format file correspond to them one by one. The safest way to determine the first N variables is to analyze the index numbers appearing in the variable names (refer to REW format naming rules).

9.1.5. LP File Format¶

Although the MPS format has more advantages compared to the LP format, the LP format is a human-readable format. If you need to observe the model structure or troubleshoot model problems, outputting the model in LP format can complete the work more efficiently. The biggest difference between LP format and MPS is that it uses arithmetic expressions to describe the objective function, constraints, and various bound information, etc.

A simple LP file example is shown below:

\Problem name:

Maximize
 OBJ: C0 + 3 C1 + 10
Subject To
 R0: 10 C0 + C1 <= 10
 R1: C0 + 10 C1 <= 10
 R2: C0 + C1 <= 1.5
Bounds
End

It looks very intuitive, and the model described is as follows:

\[\begin{split}\begin{align} Maximize \quad &C0 + 3 \cdot C1 + 10 \\ s.t. \quad &10 \cdot C0 + C1 \le 10 \\ &C0 + 10 \cdot C1 \le 10 \\ &C0 + C1 \le 1.5 \\ &0 \le C0 \le \infty \\ &0 \le C1 \le \infty \end{align}\end{split}\]

Note

MindOpt supports setting constant term in the objective function. However, some solvers in the industry like Gurobi do not support this. When using these solvers, the 10 in the above example will be treated as a variable name. Such solvers will consider this variable to have default bounds \([0, \infty)\), so the result after solving the model is Unbounded.

From the above example, we can see:

In LP files, lines starting with ‘\’ are treated as comments

LP files consist of multiple sections, with End indicating the end of the file

LP files have some punctuation symbols with special meanings, such as ‘:’, ‘+’, etc.

In LP files, we stipulate that variable and constraint names must meet certain requirements, including:

Cannot contain spaces

Cannot contain ‘:’ and ‘^’

Cannot be a valid number, such as ‘0’, ‘.0’, ‘0.’, ‘1.2E3’, ‘nan’, ‘inf’, etc.

Cannot start with the following characters: ‘*’, ‘+’, ‘-‘, ‘<’, ‘>’, ‘=’, ‘[‘, ‘]’

Cannot have the same name as keywords, or tokens within keywords (some keywords contain multiple tokens connected by spaces)

Although LP files usually have different indentations that can represent the hierarchical structure of sections, due to the relatively free nature of LP files, and often being handwritten, MindOpt does not use indentation. Instead, sections are started and ended with keywords. MindOpt requires that variable and constraint names cannot duplicate keywords (case-insensitive). The keywords are as follows:

Keywords indicating the start of the objective function section

Minimization optimization: minimize, minimum, min

Maximization optimization: maximize, maximum, max

Keywords indicating the start of the constraint section: subject to, such that, s.t., st

Keywords indicating the start of the variable bounds section: bounds, bound

Keywords indicating the start of the SOS section: sos

Keywords indicating the start of the variable type section

Binary variables: binary, binaries

General integer variables: general, generals, integer, integers

Semi-continuous variables: semi-continuous, semis, semi

Keywords indicating the end of the file: end

9.1.5.1. Objective section¶

A simple example is as follows:

Maximize
 OBJ: C0 + 3 C1 + 10

The Objective section starts with a keyword describing the optimization direction. In addition to maximize, other supported keywords are: maximum, max, as well as minimize, minimum, min.

The next one or more lines describe the objective function expression. It contains an optional objective function name ending with :, with optional spaces on both sides of :. The following objective function expressions are all valid:

3 X + Y
:3 X + Y
: 3 X + Y
 : 3 X + Y
OBJ:3 X + Y
OBJ :3 X + Y
OBJ : 3 X + Y

After the name comes the actual arithmetic expression, with multiple terms connected by ‘+’ or ‘-‘. Each term contains an optional coefficient (if no coefficient, the coefficient is 1) and an optional variable name, but at least one of the two must be present.

Note

As mentioned above, variable names cannot be valid numeric expressions, otherwise ambiguity will arise in the objective function, and MindOpt will prioritize understanding it as a constant term.

9.1.5.1.1. Quadratic Objective¶

Support for quadratic objectives is an extension of the standard LP format. A simple example is as follows:

Maximize
 OBJ: 3 X + Y + [ X ^ 2 + 2 X * Y + 3 Y ^ 2 ] / 2 + 10

In the above example, the part between ‘[‘ and ‘]’ is the quadratic objective. The writing of quadratic objectives must satisfy the following conditions:

Must appear after all linear terms and before constant term

There must be spaces before and after ‘[‘ and ‘]’, and before and after ‘*’

‘^’ can only be followed by ‘2’, and the space between ‘^’ and ‘2’ is optional

There must be ‘/ 2’ after ‘]’, with a space required between ‘/’ and ‘2’

9.1.5.1.2. Multi-objective¶

Multi-objective is also an extension of the standard LP format. A simple example is as follows:

Maximize multi-objectives
 OBJ0: Priority=1 Weight=1 AbsTol=0 RelTol=0
  X + Y
 OBJ1: Priority=2 Weight=1 AbsTol=0 RelTol=0
  X - Y

For multi-objective optimization, ‘multi-objectives’ must immediately follow the optimization direction keyword. Then multiple objectives are described, each objective must first describe the values of the 4 parameters Priority, Weight, AbsTol, RelTol. The expression must start from the next line.

Note

Variables not appearing in the objective or constraints are ignored. If these variables are really needed, coefficients of 0 can be added in the objective function.

9.1.5.2. Constraints section¶

The constraint section starts with the following keywords: subject to, such that, s.t., st.

Subject To
 R0: 10 C0 + C1 <= 10
 R1: C0 + 10 C1 <= 10
 R2: C0 + C1 + [ C0 * C1 ] <= 1.5

Like the objective function, each constraint can have an optional name, and a constraint can span multiple lines. The left side of the inequality almost follows the same rules as the objective function expression, except:

Cannot have constant term

In quadratic constraints, ‘/ 2’ is not required after the quadratic expression ends

The right side of the inequality must be a constant. Optional inequality signs are: >=, <=, ==, >, <, =. Among these, > and < are not strict greater than and less than, but are aliases for >= and <=.

Specifically, Indicator constraints in the model are also placed in the constraint section, which is also an extension of the standard LP format. It simply adds an indicator part before the linear constraint:

R0: X = 0 -> C0 + C1 <= 0

Where X = 0 -> is the indicator part, which must appear after the constraint name and before the linear constraint expression. It indicates that when the integer variable X takes the value 0, the linear constraint C0 + C1 <= 0 is activated.

Note

Variable names that do not appear in either the objective function or constraints will be ignored.

9.1.5.3. Bounds section¶

The following is an example of a Bounds section.

Bounds
 x <= 0
 y free
 -inf <= z <= 0

The Bounds section describes the boundaries of variables in the model. The default lower bound for variables is 0, and the default upper bound is \(\infty\). Each line in the Bounds section describes modifications to the boundary of a particular variable. It includes the following types (where \(l\) and \(u\) are constants, \(x\) is a variable name):

Modifying two-sided bounds

\[\begin{split}\begin{align} l \le &x \le u \\ u \ge &x \ge l \\ &x = l \\ &l = x \\ &x \space free \end{align}\end{split}\]

Modifying one-sided bound (the other side maintains the default value)

\[\begin{split}\begin{align} x &\le u \\ x &\ge l \\ l &\le x \\ u &\ge x \end{align}\end{split}\]

Note

Using “one-sided modification” expressions to set the upper bound to a negative number will result in the variable having no feasible region.

That is: x <= -1 will be understood as 0 <= x <= -1.

If the variable has no lower bound, the correct way to write it is: -inf <= x <= -1

9.1.5.4. SOS section¶

The SOS section describes the SOS constraints in the model.

SOS
 sos1: S1 :: x : 1 y : 2
 sos2: S2 :: y : 1 z : 3

Each line in the SOS section represents one constraint, starting with a constraint name (for SOS constraints, the name is not optional), followed immediately by a reserved word for constraint type:

S1: Special Ordered Set of Type 1

S2: Special Ordered Set of Type 2

This is followed by two consecutive colons, i.e., ‘::’, and then a list of variable weights, with variables and weights separated by ‘:’.

Note

Unlike objective functions and constraints, SOS constraints must have constraint names.

9.1.5.5. Variable type sections¶

There can be multiple variable type sections, and different types can each have a variable type section, meaning there can be up to 3 variable type sections. They are:

Binary variable type. Starting with binary, binaries as the section start.

General integer type. Starting with general, generals, integer, integers as the section start.

Semi-continuous type. Starting with semi-continuous, semis, semi as the section start.

Variables not mentioned in any variable type section default to continuous variables.

The variable type section format is simple, with one variable per line. The following example contains two variable type sections, declaring two binary variables and one general integer variable:

Binaries
 x
 y
Generals
 z

9.1.6. ILP File¶

ILP file is an LP file written after relaxing the original problem to make it feasible.

Note

ILP files can only be written after successfully computing IIS when the problem is infeasible. Otherwise, the API will return an error.

9.1.7. RLP File¶

This is an LP format file written after renaming variables and constraints.

It has two main typical uses:

Data anonymization. The business meaning of data may be implied in variable or constraint names. Renaming to meaningless names can hide sensitive information.

Filtering illegal names. When variables and constraints contain illegal characters, some solvers may not be able to read them. In this case, if an RLP format file is written, almost all solvers can read it.

How does RLP rename variables and constraints? It is similar to REW files.

We assume a variable’s index is i, and n constraints reference this variable. When:

It is a continuous variable, it is named: C{i}({n}), such as C0(7)

It is a general integer variable, it is named: I{i}({n})

It is a binary variable, it is named: B{i}({n})

And assuming a constraint’s index is j, then its name is c{j}. It can be seen that a constraint’s name only relates to its index number, such as c7 indicating it is the 8th constraint.

9.1.8. DLP File¶

Writing a DLP file means writing the dual problem of the current problem as an RLP file.

The variables of the dual problem correspond to the constraints of the original problem. And the constraints of the dual problem correspond to the variables of the original problem. However, trying it out will reveal that the written dual problem may not correspond to the original problem in terms of rows and columns.

In fact, we only guarantee that if the original problem has N constraints, then the first N variables in the DLP format file correspond to them one by one. The way to determine the first N variables is to analyze the index numbers appearing in the variable names (refer to RLP format naming rules).