Programowanie całkowitoliczbowe — Dokładna optymalizacja dla decyzji ciągłych i całkowitoliczbowych
- Autor metody
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- Rok
- 1958–1960
- Typ
- Mathematical optimization
- Rodzina
- Simulation / optimization
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Programowanie całkowitoliczbowe (MIP) to ramy optymalizacji matematycznej, w których niektóre zmienne decyzyjne muszą przyjmować wartości całkowite, podczas gdy inne mogą być ciągłe.
Uogólnia ono programowanie liniowe i jest szeroko stosowane w badaniach operacyjnych, logistyce, harmonogramowaniu, alokacji zasobów i projektowaniu inżynierskim, gdzie naturalnie pojawiają się ograniczenia niepodzielności — takie jak decyzje tak/nie lub ilości w całych jednostkach.
Intuicja stojąca za metodą
Wiele rzeczywistych problemów optymalizacyjnych obejmuje decyzje, których nie można podzielić — albo otwierasz obiekt, albo nie, przydzielasz dokładnie jednego pracownika do zmiany, zamawiasz całe jednostki. Ciągłe programowanie liniowe ignoruje te realia i może prowadzić do niemożliwych do wdrożenia ułamkowych odpowiedzi. MIP wymusza całkowitość bezpośrednio w modelu. Solver systematycznie bada przestrzeń dopuszczalnych rozwiązań całkowitoliczbowych za pomocą metody podziału i ograniczeń (branch-and-bound): rozwiązuje zrelaksowane podproblemy ciągłe, aby ograniczyć najlepsze możliwe rozwiązanie w każdym regionie, odrzuca regiony, które nie mogą poprawić najlepszego znalezionego rozwiązania całkowitoliczbowego, i dodaje płaszczyzny tnące, aby zawęzić przeszukiwanie. Rezultatem jest dowodnie optymalny lub prawie optymalny plan.
Historia
Podstawy programowania całkowitoliczbowego zostały położone przez Ralpha Gomory'ego, który wprowadził metodę płaszczyzn tnących w 1958 roku, oraz przez Landa i Doiga, którzy sformalizowali metodę podziału i ograniczeń w 1960 roku. W kolejnych dziesięcioleciach nastąpił rozwój teorii relaksacji LP, kombinatoryki wielościennej (Edmonds, Padberg, Grötschel), a do lat 90. komercyjne solvery sprawiły, że MIP na dużą skalę stało się praktyczne. Dziedzina ta jest kompleksowo omówiona w Nemhauser i Wolsey (1988) oraz Wolsey (1998).
Kiedy stosować
Użyj MIP, gdy Twój problem ma liniowy lub linearyzowalny cel i ograniczenia oraz obejmuje decyzje, które muszą być całkowitoliczbowe (lokalizacja obiektów, harmonogramowanie załóg, budżetowanie kapitałowe, projektowanie sieci, problemy cięcia zapasów). Jest to preferowana metoda, gdy potrzebujesz dowodnie optymalnego rozwiązania lub rozwiązania z ograniczoną luką optymalności, a rozmiar problemu jest możliwy do rozwiązania (tysiące zmiennych z nowoczesnymi solverami). NIE używaj MIP, gdy cel lub ograniczenia są silnie nieliniowe (zamiast tego użyj programowania nieliniowego lub mieszanego programowania nieliniowego całkowitoliczbowego), gdy problem jest tak duży, że metody dokładne są zbyt kosztowne (rozważ heurystyki lub metaheurystyki), lub gdy ciągłe przybliżenia są wystarczająco dokładne (użyj LP dla szybkości).
Ograniczenia i uwagi
- Złożoność w najgorszym przypadku jest NP-trudna; czas rozwiązywania może rosnąć wykładniczo wraz z liczbą zmiennych całkowitoliczbowych.
- Wymaga precyzyjnego sformułowania matematycznego; źle sformułowane modele mogą być nierozwiązywalne, nawet jeśli podstawowy problem jest możliwy do opanowania.
- Elementy nieliniowe lub niewypukłe wymagają dodatkowej linearyzacji lub specjalistycznych solverów, co zwiększa złożoność modelu.
- Koszty licencji na solvery mogą być znaczne w przypadku narzędzi komercyjnych, chociaż istnieją wysokiej jakości alternatywy open-source.
- Wyniki są tak dobre, jak model: nieprawidłowa specyfikacja ograniczeń prowadzi do bezsensownych optimum.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Tworzy dowodnie optymalne rozwiązania z kwantyfikowalną luką optymalności, umożliwiając rygorystyczne uzasadnienie decyzji.
- Natywnie obsługuje zmienne binarne i ogólne zmienne całkowitoliczbowe, odzwierciedlając rzeczywistą niepodzielność i ograniczenia logiczne.
- Nowoczesne solvery (Gurobi, CPLEX, SCIP) wykorzystują zaawansowane metody podziału i ograniczeń, płaszczyzny tnące i presolve do efektywnego obsługiwania dużych instancji.
- Przejrzysta formuła modelu sprawia, że założenia są jawne i podlegają audytowi przez ekspertów dziedzinowych.
- Obsługuje analizę wrażliwości i badania parametryczne w celu zrozumienia, jak rozwiązania zmieniają się wraz z danymi wejściowymi.
- Szeroko wspierane przez języki modelowania (AMPL, GAMS, Pyomo, JuMP), umożliwiające szybkie prototypowanie.
Zastosowania
- Łańcuch dostaw i logistyka: wyznaczanie tras pojazdów, lokalizacja obiektów i optymalizacja zapasów z całkowitoliczbowymi ilościami przesyłek.
- Harmonogramowanie siły roboczej: tworzenie grafików pielęgniarek, przydzielanie załóg i planowanie zmian z binarnymi zmiennymi przypisania.
- Budżetowanie kapitałowe: wybór portfela niepodzielnych projektów inwestycyjnych z uwzględnieniem ograniczeń budżetowych.
- Telekomunikacja i projektowanie sieci: rozbudowa pojemności i routing z binarnymi decyzjami aktywacji łączy.
- Systemy energetyczne: zobowiązanie jednostek w sieciach energetycznych decydujące o tym, które generatory włączyć lub wyłączyć w każdej godzinie.
- Produkcja: ustalanie wielkości partii produkcyjnych, harmonogramowanie maszyn i problemy cięcia zapasów z całkowitoliczbowymi rozmiarami partii.
Jak to działa
Jak to działa
Zdefiniuj model optymalizacyjny: funkcję celu (liniową kombinację zmiennych decyzyjnych do minimalizacji lub maksymalizacji), liniowe ograniczenia nierównościowe i równościowe oraz wymagania całkowitości. Zmienne ciągłe obsługują ilości, które mogą być ułamkowe; zmienne binarne (0/1) lub ogólne zmienne całkowitoliczbowe obsługują decyzje dyskretne.
Wzór
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^pRozwiąż relaksację LP, tymczasowo pomijając ograniczenia całkowitości. Daje to dolne ograniczenie (dla minimalizacji) optymalnego celu MIP i kandydata na rozwiązanie, które może być ułamkowe.
Wzór
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0Wybierz ułamkową zmienną całkowitoliczbową z rozwiązania relaksacji LP. Utwórz dwa podproblemy potomne, dodając ograniczenie podłogi w jednym i ograniczenie sufitu w drugim, dzieląc przestrzeń dopuszczalną bez utraty żadnego punktu całkowitoliczbowo-dopuszczalnego.
Wzór
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceilRozwiąż relaksację LP każdego podproblemu. Jeśli ograniczenie jest gorsze niż najlepsze znalezione dotychczas rozwiązanie całkowitoliczbowe (incumbent), odrzuć tę gałąź. Jeśli rozwiązanie LP okaże się całkowitoliczbowo-dopuszczalne, zaktualizuj incumbent, jeśli poprawia ono cel.
Wzór
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}Opcjonalnie dodaj płaszczyzny tnące — ważne nierówności, które odcinają ułamkowe rozwiązanie LP bez usuwania żadnego punktu całkowitoliczbowo-dopuszczalnego. Cięcia Gomory'ego to klasyczne podejście; cięcia specyficzne dla problemu (np. cięcia kliki, cięcia przepływu) mogą drastycznie zmniejszyć rozmiar drzewa.
Wzór
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}Zatrzymaj się, gdy drzewo podziału i ograniczeń zostanie w pełni przeszukane lub gdy luka między najlepszym rozwiązaniem całkowitoliczbowym a globalnym dolnym ograniczeniem spadnie poniżej tolerancji określonej przez użytkownika (np. 0,01%). Zwróć rozwiązanie incumbent wraz z certyfikatem optymalności.
Wzór
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilonCzęste pułapki
- Ustawienie zbyt wąskiej tolerancji luki optymalności może spowodować, że solver będzie działał w nieskończoność; zawsze ustawiaj praktyczną lukę (np. 1%) dla dużych instancji.
- Symetria w modelu (np. zamienne obiekty) tworzy redundantne gałęzie i rozdmuchuje drzewo przeszukiwania — użyj ograniczeń łamiących symetrię.
- Słabe relaksacje LP (duża luka całkowitości) prowadzą do bardzo dużych drzew podziału i ograniczeń; zainwestuj czas w dodawanie ważnych nierówności lub zaostrzenie formuły.
- Traktowanie wszystkich zmiennych jako całkowitoliczbowych, gdy tylko niektóre muszą takie być, jest niepotrzebnie kosztowne; używaj zmiennych binarnych tylko tam, gdzie wymagają tego ograniczenia logiczne.
- Ignorowanie ciepłego startu z dobrym początkowym rozwiązaniem dopuszczalnym marnuje czas solvera na znalezienie pierwszego incumbent.
Najczęściej zadawane pytania
Czym MIP różni się od programowania liniowego (LP)?
LP wymaga, aby wszystkie zmienne decyzyjne były ciągłe (o wartościach rzeczywistych), co może prowadzić do rozwiązań ułamkowych, które są fizycznie niewykonalne (np. 2,7 ciężarówek). MIP dodaje ograniczenia całkowitości do niektórych lub wszystkich zmiennych, wymuszając rozwiązania całkowitoliczbowe lub binarne kosztem większej złożoności obliczeniowej.
Kiedy powinienem użyć heurystyki zamiast MIP?
Gdy problem ma miliony zmiennych, silnie nieliniową strukturę lub wymaga rozwiązania w czasie zbliżonym do rzeczywistego, dokładne MIP może być zbyt wolne. Metaheurystyki (algorytmy genetyczne, symulowane wyżarzanie) mogą szybko generować dobre rozwiązania, ale bez gwarancji optymalności. MIP jest preferowane, gdy certyfikacja jakości rozwiązania ma znaczenie.
Czym jest luka optymalności i jak mała powinna być?
Luka to (cel incumbent - ograniczenie LP) / ograniczenie LP, wyrażona w procentach. Certyfikuje ona, jak daleko najlepsze znane rozwiązanie całkowitoliczbowe może być od prawdziwego optimum. Dla większości praktycznych zastosowań wystarczająca jest luka 0,1–1%; węższe luki wymagają wykładniczo więcej czasu solvera.
Czy MIP może obsługiwać nieliniowe cele lub ograniczenia?
Standardowe MIP zakłada liniowość. Nieliniowe zależności muszą być linearyzowane (np. aproksymacja liniowa odcinkami, binarne rozszerzenie produktów) lub obsługiwane przez solvery mieszanego programowania nieliniowego całkowitoliczbowego (MINLP), które są znacznie trudniejsze do rozwiązania.
Które solvery są zalecane dla MIP?
Komercyjne: Gurobi i CPLEX to wzorce branżowe. Open-source: SCIP, CBC (poprzez COIN-OR) i HiGHS są konkurencyjne dla problemów o umiarkowanej wielkości. Wszystkie obsługują standardowe interfejsy modelowania, takie jak AMPL, Pyomo i JuMP.
Pokrewne metody
Źródła
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN: 9780471359432Skopiowano.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Skopiowano.