Speciální objednaná sada - Special ordered set

v diskrétní optimalizace, a speciální objednaná sada (SOS) je objednaný soubor proměnných, které se používají jako další způsob k určení podmínek integrity v optimalizačním modelu. Sady speciálních objednávek jsou v zásadě zařízení nebo nástroje používané v větev a svázaný metody větvení na množinách proměnných, spíše než na jednotlivých proměnných, jako v běžných smíšených celočíselné programování. Vědět, že proměnná je součástí a soubor a že je objednal dává algoritmu větve a vázanosti inteligentnější způsob, jak čelit problému s optimalizací, a pomáhá urychlit postup hledání. Členy speciální uspořádané množiny jednotlivě mohou být spojité nebo diskrétní proměnné v jakékoli kombinaci. Avšak i když jsou všechny členy samy spojité, model obsahující jednu nebo více speciálních uspořádaných sad se stává problémem diskrétní optimalizace vyžadujícím smíšené celé číslo optimalizátor pro jeho řešení.

„Jedinou“ výhodou používání speciálních objednaných sad ve srovnání s použitím pouze omezení je, že postup hledání bude obecně znatelně rychlejší.[1]

Podle J.A. Tomlin,[2] Sady speciálních objednávek poskytují mocný prostředek k modelování nekonvexních funkcí a diskrétních požadavků, i když existuje tendence myslet na ně pouze z hlediska programování nuly jedna s možností výběru více možností.

Kontext aplikací

  • Programování s možností výběru z více možností
  • Globální optimalizace s nepřetržitými oddělitelnými funkcemi.

Dějiny

Původ konceptu byl v článku Beale s názvem „Dva dopravní problémy“ (1963)[3] kde představil model hodnocení nabídky, termín však poprvé výslovně zavedli Beale a Tomlin (1970).[4] Sada speciálních objednávek byla poprvé implementována v matematickém programovacím systému UMPIRE společnosti Scicon.[5]

Sady zvláštních objednávek byly důležitým a opakujícím se tématem v díle Martina Bealeho,[6] a jejich hodnota byla rozpoznána do bodu, kdy téměř všechny produkční matematické programovací systémy (MPS) implementují nějakou verzi nebo podmnožinu SOS.

Druhy SOS

Existují dva druhy speciálních objednaných sad:

  1. Speciální objednané sady typu 1 (SOS1 nebo S1): jsou nanejvýš množinou proměnných jeden z nichž může mít nenulovou hodnotu, všechny ostatní jsou na 0. Nejčastěji se používají tam, kde sada proměnných je ve skutečnosti proměnnými 0-1: jinými slovy, musíme si vybrat nejvýše jednu ze souboru možností. Mohou nastat například tam, kde se rozhodujeme o tom, jakou velikost továrny postavit, když máme sadu možností, možná malou, střední, velkou nebo vůbec žádnou, a pokud se rozhodneme postavit továrnu, musíme si vybrat jedna a pouze jedna velikost.
  2. Speciální objednané sady typu 2 (SOS2 nebo S2): uspořádaná sada nezáporných proměnných, z nichž nejvýše dva mohou být nenulové, a pokud jsou dvě nenulové, musí být v jejich pořadí za sebou. Speciální objednané sady typu 2 se obvykle používají k modelování nelineárních funkcí proměnné v lineárním modelu. Jsou přirozeným rozšířením konceptů Oddělitelné programování, ale pokud jsou vloženy do kódu pobočky a vazby, umožňují najít skutečně globální optima, nejen místní optima.

Další příklad

Poznámky

  1. ^ Christelle Gueret, Christian Prins, Marc Sevaux, „Aplikace optimalizace pomocí Xpress-MP“, Editions Eyrolles, Paříž, Francie (2000), ISBN  0-9543503-0-8, str. 39-42 Odkaz na 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, „Dva dopravní problémy“, in: G. Kreweras a 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 a J.A. Tomlin, „Speciální zařízení v obecném matematickém programovacím systému pro nekonvexní problémy využívající uspořádané sady proměnných“, 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 a J.A. Tomlin, „Praktické řešení velkých problémů se smíšeným celočíselným programováním pomocí UMPIRE“, Management Sci. 20 (1974) 736-773
  6. ^ M.J.D. Powell, „Biografická monografie Evelyn Martin Lansdowne Beale, FRS“, Biografické monografie členů Královské společnosti 33 (1987)

Reference