Special ordered set
From Wikipedia, the free encyclopedia
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 have to choose one from a set of possibilities. These might arise for instance where we are deciding on what size 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 at most 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 are the natural extension of the concepts of Separable Programming, but when embedded in a Branch and Bound code enable truly global optima to be found, and not just local optima.
[edit] 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.
