Man Linux: Main Page and Category List

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