MPS (format)

MPS (Mathematical Programming System) is a file format for presenting and archiving linear programming (LP) and mixed integer programming problems.

Overview

right|thumb|352px|[[Argonne National Laboratory#User facilities|NEOS input statistics for January 2011.]]

The format was named after an early IBM LP product and has emerged as a de facto standard ASCII medium among most of the commercial LP solvers. Essentially all commercial LP solvers accept this format, and it is also accepted by the open-source COIN-OR system. Other software may require a customized reader routine in order to read MPS files. However, with the acceptance of algebraic modeling languages MPS usage has declined. For example, according to the NEOS server statistics in January 2011 less than 1% of submissions were in MPS form compared to 59.4% of AMPL and 29.7% of GAMS submissions.

MPS is column-oriented (as opposed to entering the model as equations), and all model components (variables, rows, etc.) receive names. MPS is an old format, so it is set up for punch cards: Fields start in column 2, 5, 15, 25, 40 and 50. Sections of an MPS file are marked by so-called header cards, which are distinguished by their starting in column 1. Although it is typical to use upper-case throughout the file for historical reasons, many MPS-readers will accept mixed-case for anything except the header cards, and some allow mixed-case anywhere. The names that you choose for the individual entities (constraints or variables) are not important to the solver; one should pick meaningful names, or easy names for a post-processing code to read.

MPS format

Here is a little sample model written in MPS format (explained in more detail below):

NAME TESTPROB

ROWS

N COST

L LIM1

G LIM2

E MYEQN

COLUMNS

XONE COST 1 LIM1 1

XONE LIM2 1

YTWO COST 4 LIM1 1

YTWO MYEQN -1

ZTHREE COST 9 LIM2 1

ZTHREE MYEQN 1

RHS

RHS1 LIM1 5 LIM2 10

RHS1 MYEQN 7

BOUNDS

UP BND1 XONE 4

LO BND1 YTWO -1

UP BND1 YTWO 1

ENDATA

For comparison, here is the same model written out in an equation-oriented format:

Optimize

COST: XONE + 4*YTWO + 9*ZTHREE

Subject To

LIM1: XONE + YTWO <= 5

LIM2: XONE + ZTHREE >= 10

MYEQN: - YTWO + ZTHREE = 7

Bounds

XONE <= 4

-1 <= YTWO <= 1

End

As mentioned below, the lower bound on XONE is either zero or -infinity, depending upon implementation, because it is not specified. Strangely, nothing in MPS format specifies the direction of optimization, and there is no standard "default" direction; some LP solvers will maximize if not instructed otherwise, others will minimize, and still others put safety first and have no default and require a selection somewhere in a control program or by a calling parameter. If the model is formulated for minimization and the solver requires maximization (or vice versa), it is easy to convert between the two by negating all coefficients of the objective function. The optimal value of the objective function will then be the negative of the original optimal value, but the values of the variables themselves will be correct. Some programs support specifying minimization/maximization within the MPS file.

OBJSENSE

MAX

MPS Sections

The NAME section starts with the word Name in columns 1-4 and the title for the problem in columns 15–21.

The optional OBJSENSE section defines if the LP problem is a maximization or minimization problem. This section is particularly useful when the default behavior (minimization) is not desired.

The ROWS section defines the names of all the constraints; entries in column 2 or 3 are E for equality ( = ) rows, L for less-than ( <= ) rows, G for greater-than ( >= ) rows, and N for non-constraining rows. The order of the rows named in this section is unimportant, except for non-constraining rows marked N, the first of which would be interpreted as the objective function.

The COLUMNS section contains the entries of the A-matrix. All entries for a given column must be placed consecutively, although within a column the order of the entries (rows) is irrelevant. Rows not mentioned for a column are implied to have a coefficient of zero.

The RHS section allows one or more right-hand-side vectors to be defined; there is seldom more than one. In the above example, the name of the RHS vector is RHS1, and has non-zero values in all 3 of the constraint rows of the problem. Rows not mentioned in an RHS vector would be assumed to have a right-hand-side of zero.

The optional RANGES specifies double-inequalities for the rows lower and upper bounds. If an integer variable has no upper bound specified, its upper bound may default to one rather than to plus infinity.

Alternatively, some mps solvers allow other categories to enhance the functionality. such as Integrality markers to mark integer variables with keywords 'MARKER' 'INTORG', 'Marker' 'INTEND' SMPS is a specialized extension, designed to represent stochastic programming problem instances, in use especially in research environments.

Although some extensions are not standardized, the format is still in general use.

Overview

MPS format

MPS Sections

See also

References