Programowanie całkowitoliczbowe — IP i programowanie mieszane całkowitoliczbowe (MIP)
- Autor metody
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Rok
- 1958
- Typ
- Mathematical optimisation — exact combinatorial method
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie całkowitoliczbowe (IP), nazywane również programowaniem mieszanym całkowitoliczbowym (MIP), gdy tylko niektóre zmienne są ograniczone do liczb całkowitych, jest gałęzią optymalizacji matematycznej, w której niektóre lub wszystkie zmienne decyzyjne muszą przyjmować wartości całkowite lub binarne.
Opierając się na programowaniu liniowym, zostało sformalizowane poprzez metodę płaszczyzn tnących Ralpha Gomory'ego (1958) oraz algorytm podziału i ograniczeń (branch-and-bound) Landa i Doiga (1960), i od tego czasu stało się standardową, dokładną ramą dla problemów harmonogramowania, przypisywania, trasowania i alokacji zasobów.
Intuicja stojąca za metodą
Zwykłe programowanie liniowe znajduje najlepszy punkt w ciągłym obszarze dopuszczalnym. Jednak wiele rzeczywistych decyzji ma charakter dyskretny — nie można zatrudnić 2,7 pielęgniarek ani otworzyć połowy magazynu. Programowanie całkowitoliczbowe dodaje ograniczenie, że niektóre lub wszystkie zmienne muszą być liczbami całkowitymi (lub binarnymi wyborami 0/1). Ceną tego ograniczenia jest złożoność obliczeniowa: zbiór dopuszczalny nie jest już gładką powierzchnią, lecz rozproszonym zbiorem punktów, a znalezienie najlepszego może wymagać zbadania ogromnej liczby potencjalnych rozwiązań. Solvery radzą sobie z tym, inteligentnie dzieląc problem na mniejsze podproblemy (rozgałęzianie) i odcinając gałęzie, które nie mogą pobić najlepszego znalezionego rozwiązania (ograniczanie), jednocześnie zacieśniając ciągłą aproksymację poprzez dodane nierówności (płaszczyzny tnące).
Historia
Programowanie całkowitoliczbowe pojawiło się pod koniec lat 50. XX wieku, gdy badacze dążyli do rozszerzenia programowania liniowego na decyzje dyskretne. Ralph Gomory wprowadził systematyczną metodę płaszczyzn tnących w 1958 roku, udowadniając, że każdy program całkowitoliczbowy mógłby być w zasadzie rozwiązany poprzez dodanie skończonej liczby cięć. Land i Doig (1960) sformalizowali metodę podziału i ograniczeń (branch-and-bound), która stała się dominującym algorytmem dokładnym. Wolsey (1998) oraz Nemhauser i Wolsey (1988) dostarczyli kanoniczne podręcznikowe opracowania, na których dziedzina nadal się opiera. Praktyczna rewolucja nastąpiła wraz z rozwojem solverów branch-and-cut w latach 90., łączących obie techniki z zaawansowanymi heurystykami, a później z eksplozją wydajności komercyjnych i otwartych solverów, co umożliwia dziś wielkoskalowe zastosowania w świecie rzeczywistym.
Kiedy stosować
Używaj programowania całkowitoliczbowego, gdy decyzje są z natury dyskretne — binarne wybory tak/nie, ilości całkowite lub logiczne ograniczenia włącz/wyłącz — i gdy potrzebujesz dokładnego lub prawie dokładnego rozwiązania optymalnego z możliwym do udowodnienia ograniczeniem jakości. Nadaje się do harmonogramowania, przydzielania załóg i zasobów, trasowania pojazdów, lokalizacji obiektów, budżetowania kapitałowego i wyboru portfela. Nie ma wymogu minimalnej wielkości próbki, ponieważ IP jest deterministyczną ramą optymalizacji, a nie procedurą wnioskowania statystycznego. Typy zmiennych mogą być binarne, kategoryczne (kodowane jako binarne) lub ciągłe (w przypadku mieszanym całkowitoliczbowym). Kluczowym praktycznym wymogiem jest to, aby problem mógł być modelowany za pomocą liniowej funkcji celu i liniowych ograniczeń; jeśli funkcja celu lub ograniczenia są nieliniowe, potrzebne są rozszerzenia programowania mieszanego całkowitoliczbowego nieliniowego (MINLP).
Ograniczenia i uwagi
- Programowanie całkowitoliczbowe jest ogólnie NP-trudne; czas rozwiązywania może rosnąć wykładniczo wraz z rozmiarem problemu i słabą formułą.
- Słaba relaksacja LP (duża luka całkowitoliczbowości) prowadzi do głębokich, kosztownych drzew przeszukiwania i długich czasów działania.
- Binarne rozszerzenie zmiennych kategorycznych o dużej liczności może znacznie zwiększyć rozmiar modelu.
- W przypadku bardzo dużych instancji solvery mogą wymagać wcześniejszego zakończenia z tolerancją luki, zamiast osiągnięcia zerowej luki.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Daje dokładne rozwiązania optymalne z certyfikowaną luką optymalności, w przeciwieństwie do heurystyk, które nie oferują gwarancji jakości.
- Natywnie obsługuje zmienne binarne i ogólne całkowitoliczbowe, co czyni go naturalną ramą dla decyzji kombinatorycznych.
- Ma zastosowanie w szerokim zakresie problemów dziedzinowych — harmonogramowanie, trasowanie, przypisywanie, problem plecakowy — z wykorzystaniem tych samych narzędzi matematycznych.
- Nowoczesne solvery branch-and-cut mogą rozwiązywać problemy z milionami zmiennych i ograniczeń, które dekady temu byłyby nierozwiązywalne.
Zastosowania
- Harmonogramowanie personelu i pielęgniarek — przydzielanie zmian w celu spełnienia wymagań dotyczących obsady przy jednoczesnym przestrzeganiu przepisów dotyczących godzin pracy.
- Trasowanie pojazdów i logistyka — znajdowanie tras dostaw o minimalnym koszcie z uwzględnieniem ograniczeń pojemności i okien czasowych.
- Lokalizacja obiektów — decydowanie, które magazyny lub zakłady otworzyć, aby zminimalizować całkowity koszt dystrybucji.
- Budżetowanie kapitałowe — wybór portfela projektów inwestycyjnych w ramach budżetu w celu maksymalizacji całkowitego zwrotu.
- Planowanie produkcji — określanie całkowitych wielkości partii w okresach czasu w celu zrównoważenia kosztów uruchomienia i kosztów utrzymania zapasów.
- Projektowanie sieci — wybór, które połączenia zainstalować w sieci komunikacyjnej lub transportowej.
Jak to działa
Jak to działa
Problem jest przedstawiany jako program matematyczny: definiuje się zmienne decyzyjne (które muszą być zadeklarowane jako całkowite lub binarne, jeśli problem tego wymaga), zapisuje liniową funkcję celu do minimalizacji lub maksymalizacji oraz wymienia wszystkie liniowe ograniczenia. Ścisła formuła — taka, której relaksacja ciągła (LP) jest jak najbliżej prawdziwego optimum całkowitoliczbowego — drastycznie skraca czas rozwiązywania.
Ograniczenia całkowitoliczbowe są tymczasowo pomijane w celu uzyskania relaksacji LP. Rozwiązanie tej relaksacji jest szybkie i daje ograniczenie: jej optymalna wartość jest zawsze co najmniej tak dobra jak prawdziwe optimum całkowitoliczbowe (dolne ograniczenie dla minimalizacji). Jeśli rozwiązanie relaksacji okaże się całkowitoliczbowe, problem jest rozwiązany. W przeciwnym razie luka między relaksacją a całkowitoliczbowością kieruje poszukiwaniem.
Zmienna ułamkowa w rozwiązaniu relaksacji jest wybierana, a problem jest dzielony na dwa podproblemy — jeden wymaga zaokrąglenia tej zmiennej w dół, drugi w górę. Każdy podproblem jest sam relaksowany i rozwiązywany, tworząc drzewo przeszukiwania. Gałęzie, których ograniczenie relaksacji jest gorsze niż najlepsze znalezione rozwiązanie całkowitoliczbowe, są odcinane bez dalszej eksploracji.
Płaszczyzny tnące to ważne nierówności liniowe, które odcinają część obszaru dopuszczalnego relaksacji LP, nie usuwając żadnego całkowitoliczbowego punktu dopuszczalnego. Dodanie silnych cięć (cięć Gomory'ego, nierówności pokrycia, cięć kliki) zacieśnia ograniczenie LP i zmniejsza liczbę węzłów, które solver musi zbadać.
Najlepsze całkowitoliczbowe rozwiązanie dopuszczalne znalezione we wszystkich zbadanych węzłach jest zwracane jako optimum. Raportowana jest luka optymalności — procentowa różnica między najlepszym rozwiązaniem całkowitoliczbowym a najlepszym pozostałym ograniczeniem; luka równa zero potwierdza globalną optymalność. W przypadku dużych instancji NP-trudnych, solver może zakończyć działanie wcześniej z tolerancją luki określoną przez użytkownika, zwracając rozwiązanie bliskie optymalnemu z możliwym do udowodnienia ograniczeniem.
Częste pułapki
- Deklarowanie zmiennych jako ciągłych, gdy powinny być całkowite — lub odwrotnie — po cichu generuje błędne rozwiązania; zawsze weryfikuj, czy typy zmiennych odpowiadają fizycznej rzeczywistości problemu.
- Luźna formuła z dużą luką relaksacji LP powoduje nadmierne rozgałęzianie; zainwestuj czas w zacieśnianie formuły (silne nierówności, przełamywanie symetrii) przed rozwiązywaniem.
- Ignorowanie luki całkowitoliczbowości w wynikach solvera: zgłoszona wartość funkcji celu jest tylko najlepszym znalezionym rozwiązaniem całkowitoliczbowym, niekoniecznie globalnym optimum, chyba że luka wynosi zero.
- Stosowanie IP do problemów, których funkcja celu lub ograniczenia są nieliniowe, bez odpowiedniego traktowania MINLP, doprowadzi do nieprawidłowych modeli.
- W przypadku problemów z harmonogramowaniem lub trasowaniem, brak dodania ważnych nierówności (takich jak cięcia kliki lub pokrycia) pozostawia znaczne możliwości poprawy wydajności.
Najczęściej zadawane pytania
Jaka jest różnica między IP a MIP?
W czystym programowaniu całkowitoliczbowym (IP) każda zmienna decyzyjna musi być liczbą całkowitą. W programowaniu mieszanym całkowitoliczbowym (MIP) niektóre zmienne są całkowite lub binarne, podczas gdy inne mogą być ciągłe. MIP jest bardziej ogólną i częściej stosowaną w praktyce ramą, ponieważ większość rzeczywistych problemów łączy dyskretne wybory z ciągłymi wielkościami.
Dlaczego programowanie całkowitoliczbowe jest NP-trudne, skoro programowanie liniowe jest wielomianowe?
Programowanie liniowe optymalizuje na wypukłym wielościanie i może być rozwiązane w czasie wielomianowym za pomocą metod simplex lub punktu wewnętrznego. Dodanie ograniczeń całkowitoliczbowych niszczy tę wypukłość: zbiór dopuszczalny staje się skończonym, ale potencjalnie astronomicznie dużym zbiorem punktów całkowitoliczbowych, i nie jest znany żaden algorytm wielomianowy, który ogólnie znajdowałby najlepszy z nich. Relaksacja LP dostarcza ograniczenia, ale nie bezpośredniego rozwiązania.
Skąd mam wiedzieć, czy moje rozwiązanie jest optymalne?
Solver raportuje lukę optymalności — procentową różnicę między najlepszym znalezionym rozwiązaniem całkowitoliczbowym a najlepszym pozostałym dolnym ograniczeniem. Luka 0% potwierdza globalną optymalność. W przypadku dużych problemów można ustawić tolerancję luki (np. 1%) i zaakceptować rozwiązanie bliskie optymalnemu; ograniczenie nadal gwarantuje, że prawdziwe optimum nie może być lepsze o więcej niż ten procent.
Co sprawia, że formuła jest „ścisła” i dlaczego to ma znaczenie?
Ścisła formuła to taka, której relaksacja LP daje ograniczenie bliskie optimum całkowitoliczbowemu, pozostawiając małą lukę całkowitoliczbowości. Gdy luka jest mała, metoda podziału i ograniczeń musi zbadać mniej węzłów i kończy działanie szybciej. Dodanie ważnych nierówności, takich jak cięcia Gomory'ego, nierówności pokrycia lub cięcia kliki, zacieśnia formułę i często jest najbardziej skutecznym sposobem na przyspieszenie solvera.
Pokrewne metody
Źródła
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN: 9780471283669Skopiowano.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN: 9780471359432Skopiowano.