Special_ordered_set
Special ordered set
Special case of discrete optimization
In discrete optimization, a special ordered set (SOS) is an ordered set of variables used as an additional way to specify integrality conditions in an optimization model. Special order sets are basically a device or tool used in branch and bound methods for branching on sets of variables, rather than individual variables, as in ordinary mixed integer programming. Knowing that a variable is part of a set and that it is ordered gives the branch and bound algorithm a more intelligent way to face the optimization problem, helping to speed up the search procedure. The members of a special ordered set individually may be continuous or discrete variables in any combination. However, even when all the members are themselves continuous, a model containing one or more special ordered sets becomes a discrete optimization problem requiring a mixed integer optimizer for its solution.
The ‘only’ benefit of using Special Ordered Sets compared with using only constraints is that the search procedure will generally be noticeably faster.[1] As per J.A. Tomlin, Special Order Sets provide a powerful means of modeling nonconvex functions and discrete requirements, though there has been a tendency to think of them only in terms of multiple-choice zero-one programming.[2]