This subroutine reads an MPS file containing a linear programming problem or a quadratic programming problem.

This derived type stores the constraint and Hessian matrices in a simple sparse matrix format of derived type s_SparseMatrixElement defined in the interface module mp_types. s_SparseMatrixElement consists of three components; a row index, a column index, and a value. For each non-zero element in the constraint and Hessian matrices an element of derived type s_SparseMatrixElement is stored. The following code fragment expands the sparse constraint matrix of the derived type s_SparseMatrixElement contained in mps, a derived type of type s_MPS, into a dense matrix:

The IMSL derived type d_MPS is the double precision counterpart to s_MPS. The IMSL derived type d_SparseMatrixElement is the double precision counterpart to s_SparseMatrixElement.

To release the space allocated for this derived type use the following statement:

An MPS file defines a linear or quadratic programming problem.

A linear programming problem is assumed to have the form:

A quadratic programming problem is assumed to have the form:

The following table maps this notation into the components in the derived type returned by READ_MPS:

If the MPS file specifies an equality constraint or bound, the corresponding lower and upper values in the returned derived type 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 component of the derived type is set to -1.0e+30. If the upper limit is missing, then the corresponding component of the derived type is set to +1.0e+30.

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:

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.

Sections must occur in the above order.

MPS keywords, section names and indicator values, are case insensitive. Row, column and set names are case sensitive.

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

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:

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.

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.

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.

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.

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, ri, defined in this section. The right-hand side value, bi, is defined in the RHS section. The two-sided constraints for row i are given in the following table:

The optional BOUNDS section defines bounds on the variables. By default, the bounds are 0 ≤ xi ≤ ∞. 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 ≤ xi ≤ 6, use a LO bound with value 2 to set 2 ≤ xi and a UP bound with value 6 to add the condition xi ≤ 6.

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

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

The bound type names are not case sensitive.

If the bound type is UP or UI and bj < 0 then the lower bound is set to ‑∞.

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.

The ENDATA section ends the MPS file.

See Example 2 of DENSE_LP.