man mps-lp-solve (Formats) - file format for linear programming problems

NAME

mps - file format for linear programming problems

DESCRIPTION

The MPS file format was introduced for an IBM program, but has also been accepted by most subsequent linear programming codes.

One standard form for a linear programming problem is as follows: 

minimize
          c'x
under the constraints 
          Ax = b 
and       x >= 0
where x is a vector of unknowns, c is the cost (or objective) vector, c' is the transpose of c, and A is a constraint matrix with m rows and n columns.

Alternately, the constraints may be defined as 

            Ax < b
and the goal may be to maximize c'x. Unfortunately, nothing in the MPS file format specifies whether the objective is to be minimized or maximized, and different programs have different defaults for this. On the other hand, it is trivial to restate a maximization problem as a minimization problem: just reverse the sign of each element of c.

The feasible region described by the constraints is a polytope, or simplex, and at least one member of the solution set lies at a vertex of this polytope.

The MPS file format is column-oriented, designed for use with punched cards. All numerical values should include a decimal point. MPS files are typically all upper-case, though many MPS readers accept mixed case anywhere except the headers, and some accept mixed case anywhere. The file layout is suggested in the following table: 

Field:      1        2          3        4       5        6
Columns:   2-3      5-12      15-22    25-36   40-47    50-61

NAME problem_name ROWS type name COLUMNS col_name row_name value row_name value RHS rhs_name row_name value row_name value RANGES range_name row_name value row_name value BOUNDS type bound_name col_name value ENDATA Here are the details on each of the seven sections:

NAME

This section consists of a single card, with "NAME" in columns 1-4 and the title of the problem in columns 15-22.

ROWS

This section describes the rows of the constraint matrix, and the objective function. It starts with a card with "ROWS" in columns 1-4. There is an additional card for each row in the constraint matrix, plus one for the objective function. Each of these cards has a type in column 2 or 3, as follows:

E
Equality
L
Less than or equal
G
Greater than or equal
N
no restriction. The first N-type row encountered is regarded as the objective, unless it is explicitly identified in the control commands.

Linear combinations of rows may also be specified. In this case the above row types are denoted respectively by the codes DE, DL, DG, and DN, in columns 2-3. Field 2 contains the linear combination rowname. Fields 3-6 contain the rowname(s) (fields 3 and 5) and their multiplier(s) (fields 4 and 6) which form the combination. A linear combination of three or more rows requires additional cards, following the first card contiguously. In the additional cards field 1 is empty. (The right-hand sides of a linear combination row must be specified in the RHS section, described below.)

The order of the cards in the ROWS section is not significant.

COLUMNS

This section defines the names of the variable, the coefficients of the objective, and all the nonzero matrix elements Aij. The section starts with a card with COLUMNS in columns 1-7, followed by data cards which may have one or two matrix elements per card. The data are entered column by column, and all the data cards for the nonzero entries in each column must be grouped together contiguously. Within a column, the order of the entries is irrelevant. Rows not mentioned are assumed to have coefficients of zero.

The data card has the column label in field 2 (columns 5-12), the row label in field 3 (columns 15-22), and the value of the coefficient Aij (or cj) in field 4 (columns 25-36). Remember that the coefficient should include a decimal point. If more than one nonzero row entry for the same column is to be made on the card, then field 5 (columns 40-47) has the next row label and field 6 (columns 50-61) has its corresponding coefficient value. It should be emphasized that the use of fields 5 and 6 is optional.

There is no need to specify columns for slack variables; this is taken care of automatically having defined the row types.

A mixed integer program requires the specification of which variables are required to be integer. Markers are placed in the COLUMNS section to indicate the start and end of a group of integer variables. The start marker has its name in field 2, "MARKER" in field 3, and "INTORG" in field 5. The end marker has its name in field 2, "MARKER" in field 3, and "INTEND" in field 5.

RHS

This section supplies the elements of the right-hand side. The section starts with a card with "RHS" in columns 1-3. Since the right-hand side can be regarded as another column of the matrix, the data cards specifying the nonzero entries are in exactly the same format as the COLUMNS data cards, except that field 2 (columns 5-12) has a label for the right-hand side. More than one right-hand side may thus be specified in this section; the one to be used for the current run is specified separately. Rows not mentioned in the RHS section are assumed to have a right-hand-side of zero.

RANGES (optional)

The RANGES section is for constraints of the form

hi <= Ai1 x1 + Ai2 x2 + ... Ain xn <= ui

i.e. both an upper and lower bound exist for the row. The range of the constraint is

ri = ui - hi

The value of ui or hi is specified in the RHS section data, and the value of ri is specified in the RANGES section data. This information, plus the row type specified in the ROWS section, defines the bounds ui and hi.

If bi is the number entered in the RHS section and ri is the number specified in the RANGES section, the ui and hi are defined as follows: 

Row type    Sign of ri   Lower limit, hi  Upper limit, ui
G (>=)      + or -       bi               bi + |ri|
L (<=)      + or -       bi - |ri|        bi
E (=)       +            bi               bi + |ri|
E (=)       -            bi - |ri|        bi
The section starts with a card with "RANGES" in columns 1-6. The data cards specifying the values of ri are in the same format as the COLUMNS data cards, except field 2 (columns 5-12) has a label for the column of ranges (which can also be regarded as another column of the matrix). More than one column of ranges may be specified, but all the data cards for each column must be grouped together contiguously.

BOUNDS (optional)

The BOUNDS section specifies bounds on the variables. This is an alternative to defining extra rows in the matrix. The section starts with a card with "BOUNDS" in columns 1-6. Each card has a type code in field 1 (columns 2-3). The type codes, and the resulting bounds, are as follows:

LO
Lower bound: value <= x (< infinity)
UP
Upper bound: (0 <=) x <= value
FX
Fixed variable: x = value
FR
Free variable
MI
Lower bound is minus infinity: -infinity <= x (<= 0)
PL
upper bound is plus infinity (default): (0 <=) x < infinity
BV
Binary variable: x = 0 or 1 Field 2 (columns 5-12) specifies, a bounds row name. Field 3 (columns 15-22) specifies a column label j, corresponding to the variable xj. Field 4 (columns 25-36) specifies a bound value bj. Fields 5 and 6 are blank.

When bounds are not specified for a column, or the entire BOUNDS section is omitted, the usual bounds, 0 <= xi <= infinity, are assumed. More than one bound for a given variable may be entered, i.e. both a lower and an upper bound. When only one is specified the other is assumed to be one of the default values of 0 or infinity, as shown in parentheses above.

ENDATA

This section consists of a single card with "ENDATA" in columns 1-6. Note the odd spelling.

EXAMPLE

Suppose we want to minimize

XONE + 4 YTWO + 9 ZTHREE (COST)

subject to 

	XONE + YTWO <= 5               (LIM1)
	XONE + ZTHREE >= 10            (LIM2)
	- YTWO + ZTHREE  = 7          (MYEQN)
	0 <= XONE <= 4
	-1 <= YTWO <= 1
This problem is represented by the following MPS file: 
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

SEE ALSO

http://www.mcs.anl.gov/home/otc/Guide/faq/linear-programming-faq.html

http://www.mcs.anl.gov/otc/Server/lp/mps/mps.html