# MPS Format

MPS 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, but if you are using public domain software and have MPS files, you may need to write your own reader routine for this.

The main things to know about MPS format are that it is column oriented (as opposed to entering the model as equations), and everything (variables, rows, etc.) gets a name. MPS is a very old format, so it is set up as though you were using 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, 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; you should pick names that are meaningful to you, or will be easy for a post-processing code to read.

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
0 < = XONE < = 4
-1 < = YTWO < = 1
End



Strangely, there is nothing in MPS format that specifies the direction of optimization. And there really is no standard "default" direction; some LP codes will maximize if you don't specify otherwise, others will minimize, and still others put safety first and have no default and require you to specify it somewhere in a control program or by a calling parameter. If you have a model formulated for minimization and the code you are using insists on maximization (or vice versa), it may be easy to convert: just multiply all the coefficients in your objective function by (-1). The optimal value of the objective function will then be the negative of the true value, but the values of the variables themselves will be correct.

The NAME card can have anything you want, 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 largest part of the file is in the COLUMNS section, which is the place where the entries of the A-matrix are put. 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; most people don't bother having 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 lets you put lower and upper bounds on individual variables, instead of having to impose bounds through extra 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.

There is another optional section called RANGES that specifies double-inequalities. There are also some ways to mark integer variables. The final card must be ENDATA (note the spelling).

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