Special Records in MPS Files: ILOG CPLEX Extensions

ILOG CPLEX extends the MPS standard in several ways. The following sections document extensions with respect to objective function sense, objective function name, integer variables, special ordered sets (SOSs), and quadratic coefficients.

Objective Sense and Name

ILOG CPLEX extends the MPS standard by allowing two additional sections: OBJSEN and OBJNAME. They may be specified after the NAME section. OBJSEN sets the objective function sense, and OBJNAME selects an objective function from among the free rows within the file. If neither of these sections appears in the MPS file, ILOG CPLEX assumes that the problem is a minimization and that the objective function is the first free row encountered in the ROWS section. If these options are used, they must appear in order and as the first and second sections after the NAME section. The values for OBJSENSE can be MAX or MIN.

Here is an example of these optional sections: 

NAME          example.mps

OBJSENSE      

  MAX

OBJNAME

  rowname

Integer Variables

If you are licensed to use the ILOG CPLEX mixed integer optimizer, then you may restrict any or all variables to integer values. ILOG CPLEX accepts two commonly used ways of extending the MPS file format to include integer variables: in the COLUMNS section or in the BOUNDS section.

In the first way, integer variables are identified within the COLUMNS section of the MPS file by marker lines. A marker line is placed at the beginning and end of a range of integer variables. Multiple sets of marker lines are allowed. Integer marker lines have a field format consisting of Fields 2 through 4.

Field 2: Marker name
Field 3: 'MARKER' (including the single quotation marks)
Field 4: Keyword 'INTORG' and 'INTEND' to mark beginning and end respectively (including the single quotation marks)
Fields 5 and 6 are ignored.

The marker name must differ from the preceding and succeeding column names.

If no bounds are specified for the variables within markers, bounds of 0 (zero) and 1 (one) are assumed.

In the following example, column x4 is an integer variable and looks like this in the COLUMNS section of an MPS file, according to this first way of treating integer variables: 

NAME

ROWS

 N  obj     

 L  c1      

 L  c2      

 E  c3      

COLUMNS

    x1        obj                 -1   c1                  -1

    x1        c2                   1

    x2        obj                 -2   c1                   1

    x2        c2                  -3   c3                   1

    x3        obj                 -3   c1                   1

    x3        c2                   1

    MARK0000  `MARKER'                 `INTORG'

    x4        obj                 -1   c1                  10

    x4        c3                -3.5

    MARK0001  `MARKER'                 `INTEND'

RHS

    rhs       c1                  20   c2                  30

BOUNDS

 UP BOUND     x1                  40

 LO BOUND     x4                   2

 UP BOUND     x4                   3

ENDATA

In the second way of treating integer variables, integer variables are declared in the BOUNDS section with special bound types in Field 1. The acceptable special bound types appear in Table 5.4.

Table 5.4 Special bound types for handling integer variables in MPS files
Type 
Purpose 
Special Considerations 
BV 
Binary variable 
Field 4 must be 1.0 or blank 
LI 
Integer lower bound 
Field 4 is the lower bound value and must be an integer 
SC 
Semi-continuous variable 
Field 4 is the upper bound and must be specified 
UI 
Integer upper bound 
Field 4 is the upper bound value and must be an integer 

To specify general integers with no upper bounds, use LI with the value 0.0.

For example, column x4 is an integer variable declared in the BOUNDS section of an MPS file, according to this second way of treating integer variables: 

NAME

ROWS

 N  obj     

 L  c1      

 L  c2      

 E  c3      

COLUMNS

    x1        obj                 -1   c1                  -1

    x1        c2                   1

    x2        obj                 -2   c1                   1

    x2        c2                  -3   c3                   1

    x3        obj                 -3   c1                   1

    x3        c2                   1

    x4        obj                 -1   c1                  10

    x4        c3                 -3.5

RHS

    rhs       c1                  20   c2                  30

BOUNDS

 UP BOUND     x1                  40

 LI BOUND     x4                   2

 UI BOUND     x4                   3

ENDATA

Special Ordered Sets (SOS) in MPS Files

If you are licensed to use the ILOG CPLEX mixed integer optimizer (that is, the MIP optimizer), then you may define special ordered sets (SOS) in MPS format.

The convention for SOS uses set declaration lines and member declaration lines, both of which begin in column 2 or beyond. In a set declaration line, columns 2 and 3 specify S1 or S2. In a member declaration line, column 5 or beyond specifies a variable name. Note that in an MPS file, the SOS section must follow the BOUNDS section.

If weighting information is to be provided, it is included in an optional REFROW section. SOS marker lines are used to delimit SOSs in the COLUMNS section of an MPS file.

SOSs may be defined in a separate file instead of in the MPS problem file, as explained in SOS File Format.

In the following example an SOS section is placed after the BOUNDS section:

NAME

ROWS

 N  obj     

 L  c1      

 L  c2      

 E  c3      

COLUMNS

    x1        obj                 -1   c1                  -1

    x1        c2                   1

    x2        obj                 -2   c1                   1

    x2        c2                  -3   c3                   1

    x3        obj                 -3   c1                   1

    x3        c2                   1

    x4        obj                 -1   c1                  10

    x4        c3                 -3.5

RHS

    rhs       c1                  20   c2                  30

BOUNDS

 UP BOUND     x1                  40

 LI BOUND     x4                   2

 UI BOUND     x4                   3

SOS

 S1                   10

    x1                  10000

    x2                  20000

    x4                  40000

    x5                  50000

ENDATA

REFROW Section for SOS in MPS Files

A REFROW section may be included immediately before the ROWS section. It consists of exactly one record line with the name of the reference row starting in Field 2. The specified row must also be defined in the ROWS section. The nonzeros of the reference row are used as weights within an SOS. All weights within one SOS must be unique values. A REFROW section is optional; if no reference row is specified, the weighting values 1, . . . , n is given to the n members of an SOS in the order in which they are read. In other words, without specific reference row information, it is assumed that the user has ordered the SOS variables in ascending order with respect to some relevant criterion (for example, in importance, capacity, objective weighting, or cost).

`MARKER' Lines for SOS in MPS Files

`MARKER' lines are used to delimit SOS in the COLUMNS section of an MPS file, much like using integer markers. (The single quotation mark before and after the term is necessary.) The names of the sets are ignored; they are used only to differentiate the `MARKER' line from the previous line. In other words, the name must be different from that of the previous column. The `MARKER' lines must come in pairs of an `SOSORG' and `SOSEND' surrounding the columns that are in the SOS. Optionally, in Field 1 of a `MARKER' . . . `SOSORG' line, either S1 or S2 may be specified to indicate the type of the SOS. An SOS MARKER line without an S1 or S2 indicator is assumed to denote an S1 set. Members of an SOS may or may not be integer or binary variables.

There is no requirement that there be a constraint that all members of an SOS sum to 1.0 (nor is any such constraint implicit). However, providing such a constraint in your formulation may be desirable as it may strengthen the LP relaxation of the mixed integer problem, as for example in the case of an S1 set consisting of binary variables.

In the following example, the excerpt from the COLUMNS section of an MPS file defines an SOS Type 1 set consisting of integer variables x4 and x5. 

 S1 NAME1     `MARKER'                 `SOSORG'

    x4        obj                 -1   c1                  10

    x4        c3                -3.5

    x5        c1                   5

    NAME2     `MARKER'                 `SOSEND'

The SOS 'MARKER' lines can appear between integer 'MARKER' lines (if all members of the SOS are integer), or integer 'MARKER' lines can appear between SOS 'MARKER' lines (if some members of the SOS are non-integer).

The MPS format cannot accommodate overlapping SOSs. That is, a variable cannot be a member of two special ordered sets. Overlapping SOSs can, however, be specified using the ILOG CPLEX SOS format, documented in SOS format.

Copyright © 2002 ILOG
http://www.ilog.com
 
 
 
 
Previous Page: Records in MPS Format Return to Top Next Page: Quadratic Objective Information in MPS Files