MPS (format)

From Wikipedia, the free encyclopedia

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

Contents

[edit] Overview

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 codes. Essentially all commercial LP codes accept this format, and it is also accepted by the open-source COIN-OR system. Other public domain software may require a customized reader routine in order to read MPS files, but such routines are not hard to write. See also the comment regarding the lp_solve code, in another section of this article, for the availability of an MPS reader.

MPS is column-oriented (as opposed to entering the model as equations), and all model components (variables, rows, etc.) receive names. The MIPLIB site provides a concise summary of MPS format, and a more detailed description is given in [Murtagh].

MPS is an old format, so it is set up for punch cards, and is not free format. Fields start in column 1, 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.

[edit] 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

Strangely, nothing in MPS format specifies the direction of optimization, and there is no standard "default" direction; some LP codes 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 code requires maximization (or vice versa), it is easy to convert between the two by negating all coefficients. 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.

[edit] Variables

The NAME record can have any value, starting in column 15. 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 first of which would be interpreted as the objective function). The order of the rows named in this section is unimportant.

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 BOUNDS section specifies lower and upper bounds on individual variables, if they are not given by rows in the matrix. All the bounds that have a given name in column 5 are taken together as a set. Variables not mentioned in a given BOUNDS set are taken to be non-negative (lower bound zero, no upper bound). A bound of type UP means an upper bound is applied to the variable. A bound of type LO means a lower bound is applied. A bound type of FX ("fixed") means that the variable has upper and lower bounds equal to a single value. A bound type of FR ("free") means the variable has neither lower nor upper bounds.

Another optional section called RANGES specifies double-inequalities, in a somewhat counterintuitive way not described here. Ways to mark integer variables are also beyond the scope of this article. The final card must be ENDATA.

A few special cases of the MPS standard are not consistently handled by implementations. In the BOUNDS section, if a variable is given a nonpositive upper bound but no lower bound, its lower bound may default to zero or to minus inifinity. If an integer variable has no upper bound specified, its upper bound may default to one rather than to plus infinity.

[edit] See also

[edit] References

 This article does not cite any references or sources. (June 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.