readMps¶

Reads an MPS file containing a linear programming problem or a quadratic programming problem.

Synopsis¶

readMps(filename)

mpsFree(mps)

Required Argument¶

char filename (Input): Name of the MPS file to be read.

Return Value¶

A structure containing the data read from the MPS file. To release this space use mpsFree.

The returned structure contains the following fields.

Field	Description
char `filename`	Name of the MPS file.
char `name`[9]	Name of the problem.
int `nrows`	Number of rows in the constraint matrix.
int `ncolumns`	Number of columns in the constraint matrix. This is also the number of variables.
int `nonzero`	Number of non-zeros in the constraint matrix.
int `nhessian`	Number of non-zeros in the Hessian matrix. If zero, then there is no Hessian matrix.
int `ninteger`	Number of variables required to be integer. This includes binary variables.
int `nbinary`	Number of variables required to be binary (0 or 1).
float `objective`	A `float` array of length `ncolumns` containing the objective vector.
sparse element `constraint`	An array of length `nonzeros` containing the sparse matrix representation of the constraint matrix. See below for details.
sparse element `hessian`	An array of length `nhessian` containing the sparse matrix representation of the Hessian matrix. If `nhessian` is zero, then this field is `None`.
float `lower_range`	A `float` array of length `nrows` containing the lower constraint bounds. If a constraint is unbounded below, the corresponding entry in `lower_range` is set to `negative_infinity`, defined below.
float `upper_range`	A `float` array of length `nrows` containing the upper constraint bounds. If a constraint is unbounded above, the corresponding entry in `upper_range` is set to `positive_infinity`, defined below.
float `lower_bound`	A `float` array of length `ncolumns` containing the lower variable bounds. If a variable is unbounded below, the corresponding entry in `lower_bound` is set to `negative_infinity`, defined below.
float `upper_bound`	A `float` array of length `ncolumns` containing the upper variable bounds. If a variable is unbounded above, the corresponding entry in `upper_bound` is set to `positive_infinity`, defined below.
int `variable_type`	An `int` array of length `ncolumns` containing the type of each variable. Variable types are:
	0	Continuous
	1	Integer
	2	Binary (0 or 1)
	4	Semicontinuous
char `name_objective`[9]	Name of the set in ROWS used for the objective row.
char `name_rhs`[9]	Name of the RHS set used.
char `name_ranges`[9]	Name of the RANGES set used or the empty string if no RANGES section in the file.
char `name_bounds`[9]	Name of the BOUNDS set used or the empty string if no BOUNDS section in the file.
char `name_row`	Array of length `nrows` containing the row names. The name of the i-th constraint row is `name_row[i]`.
char `name_column`	Array of length `ncolumns` containing the column names. The name of the i-th column and variable is `name_column[i]`.
float `negative_infinity`	Value used for a constraint or bound upper limit when the constraint or bound is unbounded above. This can be set using an optional argument. Default is 1.0e+30.
float `objective_constant`	Value of the constant in the objective.

This structure stores the constraint and Hessian matrices in a simple sparse matrix format. For each non-zero element in the matrix, a row index, a column index and a value are given. The following code fragment expands the sparse constraint matrix in the structure mps into a dense matrix:

# allocate a matrix
nr = mps.nrows
nc = mps.ncolumns;
matrix = empty((nr, nc), dtype=double)

# expand the sparse matrix
for k in range (0, mps.nonzeros) :
      i = mps.constraint[k].row
      j = mps.constraint[k].col
      matrix[i][j] = mps.constraint[k].val

Optional Arguments¶

nameRhs, char (Input)

Name of the RHS set to be used. An MPS file can contain multiple RHS sets.

By default, the first RHS set in the MPS file is used. This name is case sensitive.

nameRanges, char (Input)

Name of the RANGES set to be used. An MPS file can contain multiple RANGES sets.

By default, the first RANGES set in the MPS file is used. This name is case sensitive.

nameBounds, char (Input)

Name of the BOUNDS set to be used. An MPS file can contain multiple BOUNDS sets.

By default, the first BOUNDS set in the MPS file is used. This name is case sensitive.

positiveInfinity, float (Input)

Value used for a constraint or bound upper limit when the constraint or bound is unbounded above.

Default: 1.0e+30.

negativeInfinity, float (Input)

Value used for a constraint or bound lower limit when the constraint or bound is unbounded below.

Default: -1.0e+30.

Description¶

An MPS file defines a linear or quadratic programming problem.

A linear programming problem is assumed to have the form:

\[\min_{x \in R^n} c^T x\]

\[b_l \leq Ax \leq b_u\]

\[x_l \leq x \leq x_u\]

A quadratic programming problem is assumed to have the form:

\[\min_x \tfrac{1}{2} x^T Qx + c^T x\]

\[b_l \leq Ax \leq b_u\]

\[x_l \leq x \leq x_u\]

The following table maps this notation into the fields in the structure returned by the reader:

C	`Objective`
A	`Constraint`
Q	`Hessian`
$b_l$	`lower_range`
$b_u$	`upper_range`
$x_l$	`lower_bound`
$x_u$	`upper_bound`

If the MPS file specifies an equality constraint or bound, the corresponding lower and upper values in the returned structure will be exactly equal.

The problem formulation assumes that the constraints and bounds are two-sided. If a particular constraint or bound has no lower limit, then the corresponding entry in the structure is set to ‑1.0e+30. If the upper limit is missing, then the corresponding entry in the structure is set to +1.0e+30.

MPS File Format¶

There is some variability in the MPS format. This section describes the MPS format accepted by this reader.

An MPS file consists of a number of sections. Each section begins with a name in column 1. With the exception of the NAME section, the rest of this line is ignored. Lines with a ‘*’or ‘$’in column 1 are considered comment lines and are ignored.

The body of each section consists of lines divided into fields, as follows:

Field Number	Columns	Contents
1	2-3	Indicator
2	5-12	Name
3	15-22	Name
4	25-36	Value
5	40-47	Name
6	50-61	Value

The format limits MPS names to 8 characters and values to 12 characters. The names in fields 2, 3 and 5 are case sensitive. Leading and trailing blanks are ignored, but internal spaces are significant.

The sections in an MPS file are as follows.

NAME
ROWS
COLUMNS
RHS
RANGES (optional)
BOUNDS (optional)
QUADRATIC (optional)
ENDATA

Sections must occur in the above order.

MPS keywords (defined by the user in MPS data files), section names and indicator values, are case insensitive. Row, column and set names are case sensitive.

NAME Section¶

The NAME section contains the single line. A problem name can occur anywhere on the line after NAME and before columns 62. The problem name is truncated to 8 characters.

ROWS Section¶

The ROWS section defines the name and type for each row. Field 1 contains the row type and field 2 contains the row name. Row type values are not case sensitive. Row names are case sensitive. The following row types are allowed:

Row Type	Meaning
E	Equality Constraint.
L	Less than or equal constraint.
G	Greater than or equal constraint.
N	Objective or a free row.

COLUMNS Section¶

The COLUMNS section defines the nonzero entries in the objective and the constraint matrix. The row names here must have been defined in the ROWS section.

Field	Contents
2	Column name.
3	Row name.
4	Value for the entry whose row and column are given by fields.
5	Row name.
6	Value for the entry whose row and column are given by fields 5 and 2.

NOTE: Fields 5 and 6 are optional.

The COLUMNS section can also contain markers. These are indicated by the name ‘MARKER’ (with the quotes) in field 3 and the marker type in field 4 or 5.

Marker type ‘INTORG’ (with the quotes) begins an integer group. The marker type ‘INTEND’ (with the quotes) ends this group. The variables corresponding to the columns defined within this group are required to be integer.

RHS Section¶

The RHS section defines the right-hand side of the constraints. An MPS file can contain more than one RHS set, distinguished by the RHS set name. The row names here must be defined in the ROWS section.

Field	Contents
2	RHS set name.
3	Row name.
4	Value for the entry whose set and row are given by fields 2 and 3.
5	Row name.
6	Value for the entry whose set and row are given by fields 2 and 5.

If the row name is identical with the name of the objective, then the negative of the value in field 6 is the constant in the objective function.

NOTE: Fields 5 and 6 are optional.

RANGES Section¶

The optional RANGES section defines two-sided constraints. An MPS file can contain more than one range set, distinguished by the range set name. The row names here must have been defined in the ROWS section.

Field	Contents
2	Range set name.
3	Row name.
4	Value for the entry whose set and row are given by fields 2 and 3.
5	Row name.
6	Value for the entry whose set and row are given by fields 2 and 5.

NOTE: Fields 5 and 6 are optional.

Ranges change one-sided constraints, defined in the RHS section, into two-sided constraints. The two-sided constraint for row i depends on the range value, $r_i$, defined in this section. The right-hand side value, $b_i$, is defined in the RHS section. The two-sided constraints for row i are given in the following table:

Row Type	Lower Constraint	Upper Constraint
G	$b_i$	$b_i+\| r_i \|$
L	$b_i-\| r_i \|$	$b_i$
E	$b_i-\min\left( 0,r_i \right)$	$b_i+\max\left( 0,r_i \right)$

BOUNDS Section¶

The optional BOUNDS section defines bounds on the variables. By default, the bounds are $0\leq x_i\leq\infty$. The bounds can also be used to indicate that a variable must be an integer.

More than one bound can be set for a single variable. For example, to set $2\leq x_i\leq 6$ use a LO bound with value 2 to set $2\leq x_i$ and an UP bound with value 6 to add the condition $x_i\leq 6$.

An MPS file can contain more than one bounds set, distinguished by the bound set name.

Field	Contents
1	Bounds type.
2	Bounds set name.
3	Column name
4	Value for the entry whose set and column are given by fields 2 and 3.
5	Column name.
6	Value for the entry whose set and column are given by fields 2 and 5.

NOTE: Fields 5 and 6 are optional.

The bound types are as follows. Here $b_i$ are the bound values defined in this section, the $x_i$ are the variables, and I is the set of integers.

Bounded Type	Definition	Formula
LO	Lower bound	$b_j\leq x_i$
UP	Upper bound	$x_i\leq b_i$
FX	Fixed variable	$x_i=b_i$
FR	Free variable	$-\infty\leq x_i\leq\infty$
MI	Lower bound is minus infinity	$-\infty\leq x_i$
PL	Upper bound is positive infinity	$x_i\leq\infty$
BV	Binary variable (variable must be 0 or 1).	$x_i\in\{ 0,1 \}$
UI	Upper bound and integer	$x_i\leq b_i$ and $x_i\in I$
LI	Lower bound and integer	$b_i\leq x_i$ and $x_i\in I$
SC	Semicontinuous	0 or $b_i\leq x_i$

The bound type names are not case sensitive.

If the bound type is UP or UI and $b_j<0$ then the lower bound is set to $-\infty$.

QUADRATIC Section¶

The optional QUADRATIC section defines the Hessian for quadratic programming problems. The names HESSIAN, QUADS, QUADOBJ, QSECTION and QMATRIX are also recognized as beginning the QUADRATIC section.

Field	Contents
2	Column name.
3	Column name
4	Value for the entry whose row and column are given by fields 2 and 3.
5	Column name.
6	Value for the entry whose row and column are given by fields 2 and 4.

NOTE: Fields 5 and 6 are optional.

ENDATA Section¶

The ENDATA section ends the MPS file.

Row Type	Lower Constraint	Upper Constraint
G	\(b_i\)	\(b_i+\| r_i \|\)
L	\(b_i-\| r_i \|\)	\(b_i\)
E	\(b_i-\min\left( 0,r_i \right)\)	\(b_i+\max\left( 0,r_i \right)\)