Special ordered sets (SOS) in MPS files

The CPLEX extensions of MPS file format support special ordered sets (SOSs).

If you use the 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. Optionally, the name of a set is specified in column 4. 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 provided, it follows the member name in a member declaration line.

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 set1
    x1                  10000
    x2                  20000
    x4                  40000
ENDATA

'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 specified in the second field, starting in column 4 or beyond. Names of sets must be unique. 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 x5 and x6. which may be continuous or integer variables.


 S1 NAME1     ‘MARKER’                 ‘SOSORG’
    x5        obj               -9     c1     5
    x5        c2                3
    x6        obj               -6     c1      8
    x6        c3                -4.5
    NAME1     ‘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 MARKER format cannot accommodate overlapping SOSs. That is, a variable cannot be a member of two special ordered sets. Overlapping SOSs can, however, be specified by the CPLEX SOS format, documented in Special ordered sets (SOS) in MPS files.

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).