SOS1 variables and Wikipedia

In Wikipedia [1]  the following definition of a Special Ordered Set of Type 1 (SOS1) [2] is given:

Special Ordered Sets of type 1 (SOS1 or S1): are a set of variables, at most one of which can take a strictly positive value, all others being at 0.

This is not completely correct. A SOS1 member can be a negative variable or a free variable. Such a variable may take a negative value.

An example:

Model with SOS1 variables with a negative lower bound

I.e. we want to minimize \(z=\sum_i x_i\) with \(x_i \in [-i,\infty)\) while the \(x_i\)'s form a SOS1 set. The results are:

---- VAR x  

          LOWER          LEVEL          UPPER         MARGINAL

i1        -1.0000          .            +INF            1.0000      
i2        -2.0000          .            +INF            1.0000      
i3        -3.0000        -3.0000        +INF            1.0000      

                           LOWER          LEVEL          UPPER         MARGINAL

---- VAR z                 -INF           -3.0000        +INF             .          

Indeed, we see a single negative value; the others remain zero.

Definition

The correct definition is found in most manuals, e.g. the docs on OSL (a discontinued IBM product) MPS format mentions [3]:

A special ordered set (SOS) defines restrictions on the integer variables in the set. During branch-and-bound processing, branching on these sets consists of setting all variables before a certain point in the set to zero on one branch and setting all of them after a certain point to one on the alternative branch.
Three different types of special ordered sets are recognized:

• Type 1, where at most one variable in the set may take a nonzero value.

• Type 2, where at most two variables in the set may take nonzero values. If two variables are nonzero, they must be adjacent in the set. This allows the modeling of nonconvex separable functions, such as economies of scale.

• Type 3, where at most one variable in the set may take a nonzero value, and there was at least one equality row with an RHS value of 1.0 in which all the variables in the set had a coefficient of 1.0. In this case, it is possible to say that all the variables are 0-1 variables. This allows the modeling of decisions.

The SOS3 type is an extension that is not much used.

But...

Looks like there is no complete uniformity here. When doing some further tests, we found out a few solvers (GAMS/BDMLP, GAMS/LINDO) return something different:

---- VAR x  

          LOWER          LEVEL          UPPER         MARGINAL

i1        -1.0000        -1.0000        +INF            1.0000      
i2        -2.0000        -2.0000        +INF            1.0000      
i3        -3.0000        -3.0000        +INF            1.0000      

                           LOWER          LEVEL          UPPER         MARGINAL

---- VAR z                 -INF           -6.0000        +INF             .          

Using the democratic rule: "one solver, one vote" they are on the losing side of this debate. Of course it would be much better if all solvers do the same thing.

Update: LINDO has confirmed this as a bug and fixed it. The behavior of BDMLP was acknowledged as "as designed".

Notes on using SOS1 sets

These days we probably should replace SOS sets by formulations with binary variables. Often binary variable formulations perform better. For this we often need good bounds, in order to make big-M constants having tight values. Some solvers support indicator constraints and general constraints (like max, min, etc.). These constructs may introduce SOS1 variables behind the scenes.

SOS2 variables

The Wikipedia entry for SOS1 [1] has been fixed by now (thank you!). However, a similar issue is present in the section on SOS2 variables. The Wikipedia text says:

Special Ordered Sets of type 2 (SOS2 or S2): an ordered set of non-negative variables, of which at most two can be non-zero, and if two are non-zero these must be consecutive in their ordering.

Using the same model as before but replacing sos1 variable by sos2 variable we should see as solution:

---- VAR x  

          LOWER          LEVEL          UPPER         MARGINAL

i1        -1.0000          .            +INF            1.0000      
i2        -2.0000        -2.0000        +INF            1.0000      
i3        -3.0000        -3.0000        +INF            1.0000      

                           LOWER          LEVEL          UPPER         MARGINAL

---- VAR z                 -INF           -5.0000        +INF             .          

As we can see SOS2 variables can be negative. Of course in virtually all practical cases SOS2 variables will be non-negative, but it is not a requirement.

I am not sure if the emphasis in the Wikipedia text on the ordering is so useful. This may be read as \(x_i \le x_{i+1}\), which is not what SOS2 is about. I think just saying the two non-zero values must be consecutive or adjacent should be enough. Writing is not so easy!

References

1. Special Ordered Set, https://en.wikipedia.org/wiki/Special_ordered_set
2. E. M. L. Beale and J. A. Tomlin, Special Facilities in a General Mathematical Programming System for Nonconvex Problems Using Ordered Sets of Variables, Operational Research 69, pp 447–454, 1970
3. IBM Optimization Subroutine Library, Guide and Reference, Release 2, 1991
4. Wilhelm Hummeltenberg, Implementations of special ordered sets in MP software, European Journal of Operations Research, 17 (1), 1984, pp. 1-15.