Special ordered set

In discrete optimization, a special ordered set is an ordered set of variables. There are two sorts of Special Ordered Sets.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. They most frequently apply where a set of variables are actually 0-1 variables: in other words, we haveto choose one from a set of possibilities. These might arise for instance where we are deciding on whatsize of factory to build, when we have a set of options, perhaps small, medium, large or no factory at all,and we have to chose one and only one size.

Special Ordered Sets of type 2 (SOS2 or S2): an ordered set of non-negative variables, of which atmost two can be non-zero, and if two are non-zero these must be consecutive in their ordering. Special Ordered Sets of type 2 are typically used to model non-linear functions of a variable. They arethe natural extension of the concepts of Separable Programming, but when embedded in a Branch andBound code enable truly global optima to be found, and not just local optima.

References

* The notion of Special Ordered Sets was introduced by E. M. L. Beale and J. A. Tomlin. Special Facilities in a General Mathematical Programming System for Nonconvex Problems Using Ordered Sets of Variables. In J. Lawrence, editor, Operational Research 69, pages 447–454. Tavistock Publishing, London, 1970.
* E. M. L. Beale and J. J. H. Forrest. Global Optimization Using Special Ordered Sets. Mathematical Programming, 10(1):52–69, 1976.