Zestaw na specjalne zamówienie
W optymalizacji dyskretnej specjalny uporządkowany zestaw (SOS) to uporządkowany zestaw zmiennych używany jako dodatkowy sposób określania warunków integralności w modelu optymalizacji. Zestawy zamówień specjalnych to w zasadzie urządzenie lub narzędzie używane w rozgałęzień i ograniczeń do rozgałęzień na zestawach zmiennych, a nie na pojedynczych zmiennych, jak w zwykłym mieszanym programowaniu całkowitym . Wiedza, że zmienna jest częścią zbioru i że jest uporządkowana daje algorytmowi rozgałęzionemu i powiązanemu bardziej inteligentny sposób stawienia czoła problemowi optymalizacji, pomagając przyspieszyć procedurę wyszukiwania. Członkowie specjalnie uporządkowanego zestawu indywidualnie mogą być zmiennymi ciągłymi lub dyskretnymi w dowolnej kombinacji. Jednak nawet wtedy, gdy wszystkie elementy same są ciągłe, model zawierający jeden lub więcej specjalnie uporządkowanych zestawów staje się problemem optymalizacji dyskretnej, wymagającym mieszanego optymalizatora liczb całkowitych do jego rozwiązania.
„Jedyną” zaletą korzystania ze specjalnie zamówionych zestawów w porównaniu z używaniem samych ograniczeń jest to, że procedura wyszukiwania będzie generalnie zauważalnie szybsza. Według JA Tomlina, zestawy zamówień specjalnych zapewniają potężny sposób modelowania funkcji niewypukłych i wymagań dyskretnych, chociaż istniała tendencja do myślenia o nich tylko w kategoriach programowania zero-jedynkowego wielokrotnego wyboru.
Kontekst aplikacji
- Programowanie wielokrotnego wyboru
- Globalna optymalizacja z ciągłymi rozdzielnymi funkcjami.
Historia
Źródłem koncepcji był artykuł Beale'a zatytułowany „Dwa problemy transportowe” (1963), w którym przedstawił on model oceny ofert. Jednak termin ten został po raz pierwszy wyraźnie wprowadzony przez Beale'a i Tomlina (1970). Zestaw na specjalne zamówienie został po raz pierwszy zaimplementowany w systemie programowania matematycznego UMPIRE firmy Scicon.
Zestawy zamówień specjalnych były ważnym i powracającym tematem w pracach Martina Beale'a, a ich wartość została doceniona do tego stopnia, że prawie wszystkie produkcyjne systemy programowania matematycznego (MPS) implementują jakąś wersję lub podzbiór SOS.
Rodzaje SOS
Istnieją dwa rodzaje zestawów zamówionych specjalnie:
- Specjalne uporządkowane zestawy typu 1 (SOS1 lub S1): to zestaw zmiennych, z których co najwyżej jedna może przyjąć wartość różną od zera, a wszystkie inne mają wartość 0. Najczęściej mają zastosowanie, gdy zestaw zmiennych jest w rzeczywistości 0- 1 zmiennych: innymi słowy, musimy wybrać co najwyżej jedną ze zbioru możliwości. Mogą one powstać na przykład wtedy, gdy podejmujemy decyzję o wielkości fabryki do zbudowania, kiedy mamy zestaw opcji, być może małą, średnią, dużą lub brak fabryki, a jeśli zdecydujemy się zbudować fabrykę, musimy wybrać jeden i tylko jeden rozmiar.
- Specjalne uporządkowane zestawy typu 2 (SOS2 lub S2): uporządkowany zestaw nieujemnych zmiennych, z których co najwyżej dwie mogą być niezerowe, a jeśli dwie są niezerowe, to muszą być kolejne w kolejności. Specjalne uporządkowane zbiory typu 2 są zwykle używane do modelowania nieliniowych funkcji zmiennej w modelu liniowym. Są naturalnym rozszerzeniem koncepcji programowania separowalnego, ale gdy są osadzone w kodzie typu Branch and Bound, umożliwiają znalezienie prawdziwie globalnych optimów, a nie tylko optimów lokalnych.
Dalszy przykład
Notatki
- Pojęcie zestawów na zamówienie zostało wprowadzone przez EML Beale i JA Tomlin. Specjalne udogodnienia w ogólnym systemie programowania matematycznego dla problemów niewypukłych przy użyciu uporządkowanych zestawów zmiennych. W J. Lawrence, redaktor, Operational Research 69, strony 447–454. Wydawnictwo Tavistock, Londyn, 1970.
- EML Beale i JJH Forrest. Globalna optymalizacja przy użyciu specjalnie zamówionych zestawów. Programowanie matematyczne, 10 (1): 52–69, 1976.
- „Specjalne zamówione zestawy i aplikacja do planowania operacji zaopatrzenia w gaz”, JA Tomlin, Ketron Management Science, Inc., Mountain View, CA 94040-1266, USA
- Christelle Gueret, Christian Prins, Marc Sevaus, „Zastosowania optymalizacji za pomocą Xpress-MP” , Editions Eyrolles, Paryż, Francja (2000), ISBN 0-9543503-0-8 , str. 39-42
