Programowanie całkowitoliczbowe deterministyczne — optymalizacja dokładna ze zmiennymi decyzyjnymi całkowitymi
- Autor metody
- Ralph E. Gomory
- Rok
- 1958
- Typ
- Exact combinatorial 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 deterministyczne (DIP) to podejście optymalizacyjne w matematyce, które znajduje najlepsze rozwiązanie problemów, w których niektóre lub wszystkie zmienne decyzyjne muszą przyjmować wartości całkowite, przy w pełni znanych (deterministycznych) danych celu i ograniczeń.
Jest to klasyczna, niestochastyczna forma programowania całkowitoliczbowego, stanowiąca podstawę badań operacyjnych i optymalizacji kombinatorycznej od końca lat 50. XX wieku.
Intuicja stojąca za metodą
Wiele decyzji w świecie rzeczywistym jest z natury dyskretnych: otwiera się obiekt lub nie; przydziela się pracownika do zmiany lub nie. Metody optymalizacji ciągłej nie są w stanie wymusić tych wymagań dotyczących liczb całkowitych. Programowanie całkowitoliczbowe deterministyczne radzi sobie z tym, ograniczając zmienne do liczb całkowitych, podczas gdy wszystkie parametry problemu — koszty, zdolności, zapotrzebowanie — są znane z całą pewnością. Wynikiem jest dokładne, udowodnione optymalne rozwiązanie przy tym założeniu pewności, co czyni je punktem odniesienia, w porównaniu do którego porównuje się warianty stochastyczne i odporne.
Historia
Programowanie całkowitoliczbowe wyłoniło się z programowania liniowego pod koniec lat 50. XX wieku. Algorytm płaszczyzn tnących Ralpha Gomory'ego z 1958 roku był pierwszą systematyczną metodą dokładną. Równolegle z metodą rozgałęzień i ograniczeń (Land i Doig, 1960) podejścia te zdefiniowały dziedzinę. Przymiotnik 'deterministyczne' odróżnia klasyczną formułę od stochastycznego programowania całkowitoliczbowego (Birge i Louveaux, 1997) i stał się standardową terminologią w miarę proliferacji wariantów uwzględniających niepewność.
Kiedy stosować
Użyj programowania całkowitoliczbowego deterministycznego, gdy: (1) zmienne decyzyjne są z natury dyskretne (przydział, harmonogramowanie, lokalizacja obiektów, pakowanie w pojemniki, projektowanie sieci); (2) wszystkie parametry problemu są znane z całą pewnością lub mogą być wiarygodnie oszacowane jako wartości punktowe; (3) wymagane jest dokładne rozwiązanie optymalne, a nie przybliżenie heurystyczne. NIE używaj, gdy: parametry są niepewne lub zależne od scenariusza (użyj zamiast tego programowania całkowitoliczbowego stochastycznego lub odpornego); skala problemu jest tak duża, że metoda rozgałęzień i ograniczeń jest obliczeniowo niewykonalna, a heurystyki są akceptowalne; zmienne są rzeczywiście ciągłe (użyj LP); lub należy jednocześnie zrównoważyć wiele sprzecznych celów (użyj wielokryterialnego programowania całkowitoliczbowego).
Ograniczenia i uwagi
- Zakłada, że wszystkie parametry problemu są znane dokładnie — niepewność świata rzeczywistego jest ignorowana z założenia.
- Jest NP-trudne w ogólności; czas rozwiązania w najgorszym przypadku rośnie wykładniczo wraz z rozmiarem problemu.
- Duże problemy kombinatoryczne mogą wymagać godzin lub dni obliczeń nawet przy użyciu nowoczesnych solverów.
- Jakość formułowania modelu (ostrość ograniczeń, łamanie symetrii) znacznie wpływa na czas rozwiązania.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Gwarantuje udowodnione optymalne rozwiązanie w ramach założeń modelu deterministycznego.
- Naturalnie obsługuje dyskretne, kombinatoryczne struktury decyzyjne, których nie potrafią obsłużyć metody ciągłe.
- Wspierane przez dojrzałe, wysoce wydajne komercyjne i otwarte solvery (CPLEX, Gurobi, SCIP).
- Zapewnia certyfikat luki optymalności, umożliwiając zasadne wczesne zakończenie dla dużych instancji.
- Stanowi złoty standard formuł porównawczych dla wariantów heurystycznych i stochastycznych.
Zastosowania
- Planowanie i harmonogramowanie produkcji z dyskretnymi zasobami maszynowymi lub ludzkimi
- Lokalizacja obiektów: decydowanie, które magazyny lub fabryki otworzyć
- Routing pojazdów i harmonogramowanie załóg w transporcie i logistyce
- Budżetowanie kapitałowe: wybór portfela niepodzielnych projektów inwestycyjnych
- Projektowanie sieci telekomunikacyjnych z kosztami stałymi uruchomienia połączeń
- Tworzenie grafików personelu medycznego i harmonogramowanie sal operacyjnych
Jak to działa
Jak to działa
Zdefiniuj model optymalizacyjny: funkcja celu do minimalizacji (lub maksymalizacji) jako liniowa kombinacja całkowitoliczbowych zmiennych decyzyjnych, podlegająca zestawowi liniowych ograniczeń nierównościowych lub równościowych. Wszystkie współczynniki (c, A, b) są stałe i znane — to sprawia, że formuła jest deterministyczna. Zmienne binarne (0/1) są szczególnym przypadkiem decyzji tak/nie.
Wzór
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^nRozwiąż relaksację liniową, która tymczasowo pozwala zmiennym przyjmować wartości ciągłe. Daje to dolne ograniczenie optymalnej wartości całkowitej. Jeśli rozwiązanie relaksacji liniowej jest już całkowitoliczbowe, jest ono optymalne dla IP; w przeciwnym razie rozpoczyna się rozgałęzianie.
Wzór
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0Wybierz zmienną ułamkową z rozwiązania relaksacji liniowej i podziel przestrzeń dopuszczalną, dodając ograniczenie podłogi (x_j <= wartość całkowita dolna) na jednym rozgałęzieniu i ograniczenie sufitu (x_j >= wartość całkowita górna) na drugim, generując dwa podproblemy do rozwiązania rekurencyjnie.
Wzór
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilRozwiąż relaksację liniową każdego podproblemu, aby uzyskać ograniczenie. Jeśli ograniczenie węzła jest gorsze niż najlepsze znane rozwiązanie całkowitoliczbowe (kandydat), odrzuć je. Jeśli podproblem daje rozwiązanie dopuszczalne całkowitoliczbowo lepsze niż kandydat, zaktualizuj kandydata. Proces tworzy drzewo przeszukiwania typu rozgałęzień i ograniczeń.
Wzór
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}Metody płaszczyzn tnących — a zwłaszcza płaszczyzny tnące Gomory'ego — wyprowadzają dodatkowe liniowe nierówności z tablicy liniowej, które są spełnione przez wszystkie rozwiązania całkowitoliczbowe, ale naruszone przez bieżące ułamkowe rozwiązanie liniowe. Dodanie tych płaszczyzn tnących uszczelnia relaksację liniową i zmniejsza potrzebę rozgałęziania. Nowoczesne solvery łączą metody rozgałęzień i ograniczeń z płaszczyznami tnącymi w ramach metody rozgałęzień i płaszczyzn tnących (branch-and-cut).
Wzór
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}Algorytm kończy działanie, gdy wszystkie otwarte węzły zostaną odrzucone lub dadzą rozwiązania całkowitoliczbowe. Kandydat w momencie zakończenia jest udowodnionym optymalnym rozwiązaniem całkowitoliczbowym. Solvery raportują również lukę między najlepszym ograniczeniem a kandydatem, która może być użyta jako kryterium zatrzymania dla dużych problemów.
Wzór
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*Częste pułapki
- Traktowanie niepewnych parametrów jako deterministycznych wartości punktowych może prowadzić do rozwiązań, które w praktyce działają słabo — zweryfikuj to założenie przed zastosowaniem DIP.
- Słabe relaksacje liniowe (duże luki całkowitoliczbowości) prowadzą do ogromnych drzew rozgałęzień i ograniczeń; zainwestuj w poprawne nierówności i przeformułowanie przed skalowaniem.
- Eksplozja zmiennych binarnych z formuł typu big-M może numerycznie destabilizować relaksację liniową; preferuj ostrzejsze przeformułowania ograniczeń.
- Błędne utożsamianie dopuszczalności z optymalnością przy stosowaniu tolerancji luki innej niż zero — zawsze raportuj lukę wraz z wartością celu.
- Ignorowanie symetrii w modelach (np. identyczne maszyny lub pracownicy) powoduje redundantne rozgałęzianie; dodaj ograniczenia łamiące symetrię.
Najczęściej zadawane pytania
Czym programowanie całkowitoliczbowe deterministyczne różni się od programowania całkowitoliczbowego stochastycznego?
W deterministycznym IP wszystkie parametry celu i ograniczeń są stałe i znane. Stochastyczne IP jawnie modeluje niepewne parametry za pomocą rozkładów prawdopodobieństwa lub scenariuszy, generując rozwiązania, które są odporne lub optymalne w oczekiwaniu w tych scenariuszach. Deterministyczne IP jest prostsze i szybsze w rozwiązaniu, ale ignoruje niepewność.
Czy programowanie binarne jest szczególnym przypadkiem programowania całkowitoliczbowego?
Tak. Programowanie binarne (0-1) ogranicza każdą zmienną decyzyjną do {0, 1}. Jest to najczęstszy szczególny przypadek, używany do decyzji tak/nie, takich jak czy otworzyć obiekt, wybrać projekt, czy przydzielić pracownika. Ogólne programowanie całkowitoliczbowe dopuszcza dowolną nieujemną wartość całkowitą.
Kiedy powinienem przejść z deterministycznego IP na metodę heurystyczną?
Gdy drzewo rozgałęzień i ograniczeń jest zbyt duże, aby je przeszukać w akceptowalnym czasie, a luka optymalności uzyskana z dobrej heurystyki (algorytm genetyczny, wyżarzanie symulowane, przeszukiwanie dużej okolicy) jest dopuszczalna dla danej aplikacji. Raportuj i uzasadnij lukę przy odejściu od optymalizacji dokładnej.
Czy deterministyczne IP może obsługiwać nieliniowe cele lub ograniczenia?
Klasyczne deterministyczne IP zakłada liniowość (całkowitoliczbowe programowanie liniowe). Nieliniowe programowanie całkowitoliczbowe istnieje, ale jest znacznie trudniejsze; wiele form nieliniowych można zlinearyzować za pomocą pomocniczych zmiennych binarnych i przeformułowań typu big-M. Kwadratowe programowanie całkowitoliczbowe (QIP) jest bezpośrednio obsługiwane przez niektóre nowoczesne solvery.
Jakiego solvera powinienem używać do deterministycznego IP w praktyce?
Komercyjne: Gurobi lub IBM CPLEX dla najlepszej wydajności. Akademickie/otwarte: SCIP, CBC (poprzez COIN-OR) lub HiGHS. Wszystkie implementują metodę rozgałęzień i płaszczyzn tnących z automatycznym preprocessingiem. Dla użytkowników Pythona, PuLP, Pyomo lub scipy.optimize.milp zapewniają wygodne interfejsy modelowania.
Pokrewne metody
Źródła
Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.
Otwórz odnośnik DOISkopiowano.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN: 9780471283669Skopiowano.