词条 | Special ordered set |
释义 |
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
HistoryThe 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 SOSThere are two sorts of Special Ordered Sets:
Further Example
Notes1. ^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., "Proceedings 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
2 : Optimization of ordered sets|Optimization algorithms and methods |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。