Special ordered set

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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,[2] 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.

Context of Applications[edit]

  • Multiple-choice programming
  • Global Optimization with continuous separable functions.

History[edit]

The origin of the concept was in the paper of Beale titled "Two transportation problems" (1963)[3] where he presented a bid evaluation model, however, the term was first explicitly introduced by Beale and Tomlin (1970).[4] The special order set were first implemented in Scicon's UMPIRE mathematical programming system.[5]

Special Order sets were an important and recurring theme in Martin Beale's work,[6] and their value came to be recognized to the point where nearly all production mathematical programming systems (MPS's) implement some version, or subset, of SOS.

Types of SOS[edit]

There are two sorts of Special Ordered Sets:

  1. 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 choose one and only one size.
  2. 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 in a linear model. 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.

Further Example[edit]

Notes[edit]

  1. ^ Christelle Gueret, Christian Prins, Marc Sevaux, "Applications of optimization with Xpress-MP", Editions Eyrolles, Paris, France (2000), ISBN 0-9543503-0-8, pag 39-42 Link to PDF
  2. ^ J.A. Tomlin, "Special Ordered Sets and an Application to Gas Supply Operations Planning", Ketron Management Science, Inc., Mountain View, CA 94040-1266, USA
  3. ^ E.M.L. Beale, "Two transportation problems", in: G.Kreweras and G.Morlat, eds., "Proceeding of the Third International Conference on Operational Research" (Dunod, Paris and English Universities Press, London, 1963) 780-788
  4. ^ E.M.L. Beale and J.A. Tomlin, "Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables", in: J.Lawrence, ed., "Proceedings of the Fifth International Conference on Operational Research" (Tavistock Publications, London, 1970) 447-454
  5. ^ J.J.H. Forrest, J.P.H Hirst and J.A. Tomlin, "Practical solution of large mixed integer programming problems with UMPIRE", Management Sci. 20 (1974) 736-773
  6. ^ M.J.D. Powell, "A biographical memoir of Evelyn Martin Lansdowne Beale, FRS", Biographical Memoirs of Fellows of the Royal Society 33 (1987)

References[edit]