Przejdź do treści
Wróć do wyników wyszukiwania

Niezawodne programowanie mieszane całkowitoliczbowe — Optymalizacja z wykorzystaniem zmiennych całkowitoliczbowych w warunkach niepewności

Autor metody
Ben-Tal & Nemirovski; Bertsimas & Sim
Rok
1998–2004
Typ
Deterministic robust reformulation of MIP under uncertainty
Rodzina
Simulation / optimization

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Niezawodne programowanie mieszane całkowitoliczbowe (RMIP) łączy programowanie mieszane całkowitoliczbowe z optymalizacją niezawodną, aby znaleźć rozwiązania, które pozostają wykonalne i bliskie optymalnym pomimo niepewnych parametrów.

Zamiast zakładać stałe dane, chroni decyzje przed niekorzystnymi lub najgorszymi realizacjami niepewnych danych wejściowych, wykorzystując jawny zbiór niepewności do kontrolowania stopnia konserwatyzmu, jednocześnie zachowując kombinatoryczną strukturę decyzji całkowitoliczbowych.

Intuicja stojąca za metodą

Klasyczne programy mieszane całkowitoliczbowe zakładają, że wszystkie dane są dokładnie znane, ale w praktyce koszty, popyt i czasy przetwarzania ulegają wahaniom. RMIP zadaje pytanie: jakie decyzje całkowitoliczbowe i ciągłe są najlepsze, jeśli niepewne parametry przyjmują swoje najgorsze prawdopodobne wartości w określonym zakresie? Poprzez bezpośrednie osadzenie niepewności w modelu optymalizacyjnym, RMIP tworzy plany, które są uodpornione na zmienność danych bez uciekania się do wielu scenariuszy probabilistycznych. Podejście Bertsimasa-Sima z budżetem niepewności pozwala praktykom regulować między pełną niezawodnością a efektywnością w przypadku średnim, czyniąc jawny kompromis między ochroną a kosztem.

Historia

Optymalizacja niezawodna jako wykonalny paradygmat została ustanowiona przez Ben-Tala i Nemirowskiego pod koniec lat 90. dla problemów ciągłych. Bertsimas i Sim (2004) rozszerzyli ją na programy liniowe ze zbiorem budżetu niepewności, który zachowuje liniową wykonalność. Późniejsze prace zintegrowały te ramy z programowaniem całkowitoliczbowym, co doprowadziło do powstania RMIP, które zostało szeroko przyjęte w badaniach nad łańcuchem dostaw, energetyką i transportem w latach 2010.

Kiedy stosować

Użyj RMIP, gdy decyzje obejmują wybory całkowitoliczbowe lub binarne (lokalizacja obiektów, ustalanie wielkości partii, projektowanie sieci, harmonogramowanie), a niektóre parametry wejściowe są niepewne, ale rozkłady prawdopodobieństwa są niedostępne lub niewiarygodne. Jest to odpowiednie, gdy naruszenia ograniczeń są niedopuszczalne (twarde wymagania wykonalności) i preferowana jest konserwatywna, ale deterministyczna gwarancja zamiast optymalizacji wartości oczekiwanej. NIE używaj, gdy rozkłady niepewności są dobrze scharakteryzowane, a aproksymacja średniej z próby lub stochastyczny MIP jest wykonalny; gdy wszystkie zmienne decyzyjne są ciągłe (zamiast tego użyj niezawodnego LP); lub gdy zbiór niepewności jest tak duży, że model staje się niemożliwy do rozwiązania bez strategii dekompozycji.

Ograniczenia i uwagi

  • Konserwatywne z założenia — cel w najgorszym przypadku jest zazwyczaj gorszy niż cel w przypadku oczekiwanym w programowaniu stochastycznym.
  • Wybór odpowiedniego zbioru niepewności wymaga wiedzy dziedzinowej; źle dobrany zbiór prowadzi do nadmiernej lub niedostatecznej ochrony.
  • Niezawodne reformulacje mogą znacznie zwiększyć rozmiar modelu (dodatkowe zmienne i ograniczenia), zwiększając obciążenie obliczeniowe dla dużych instancji.
  • Nie dostarcza stwierdzeń probabilistycznych dotyczących wydajności rozwiązania; stochastyczny MIP jest lepiej przystosowany, gdy wymagane są probabilistyczne miary ryzyka.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Zapewnia deterministyczne gwarancje wykonalności w najgorszym przypadku bez wymagania rozkładów prawdopodobieństwa dla niepewnych parametrów.
  • Parametr budżetu niepewności (Gamma) zapewnia intuicyjną, regulowaną kontrolę nad kompromisem między niezawodnością a optymalnością.
  • Reformulacja zachowuje strukturę MIP, umożliwiając wykorzystanie dojrzałych komercyjnych solwerów i technologii branch-and-cut.
  • Ma zastosowanie do trudnych problemów kombinatorycznych, takich jak projektowanie sieci, lokalizacja obiektów i harmonogramowanie produkcji.
  • Obliczeniowo bardziej wykonalne niż pełne stochastyczne MIP z wieloma scenariuszami.

Zastosowania

  • Projektowanie sieci łańcucha dostaw w warunkach niepewnego popytu i czasów realizacji
  • Planowanie rozbudowy systemu energetycznego z niepewną generacją odnawialną
  • Lokalizacja placówek opieki zdrowotnej w warunkach niepewności popytu pacjentów
  • Harmonogramowanie załóg linii lotniczych z niepewnymi opóźnieniami lotów
  • Ustalanie wielkości partii produkcyjnych w warunkach niepewnych kosztów i czasów przetwarzania
  • Routing sieci telekomunikacyjnych z niepewnymi wolumenami ruchu

Jak to działa

Jak to działa

1

Sformułuj nominalny MIP: zidentyfikuj zmienne decyzyjne (binarne lub całkowitoliczbowe y, ciągłe x), funkcję celu i ograniczenia. Wskaż, które parametry (współczynniki kosztów, wartości prawej strony, elementy macierzy technologicznej) są niepewne i muszą być chronione.

2

Zdefiniuj zbiór niepewności U dla niepewnych parametrów. Typowe wybory to zbiory pudełkowe (zakresy interwałowe dla każdego parametru), zbiory elipsoidalne (skorelowana niepewność) lub zbiór budżetowy Bertsimasa-Sima (jednocześnie odchyla się co najwyżej Gamma parametrów), gdzie Gamma kontroluje konserwatyzm.

3

Zastąp każde niepewne ograniczenie jego niezawodnym odpowiednikiem, który musi być spełniony dla wszystkich realizacji w U. Dla niepewności budżetowej prowadzi to do możliwej do rozwiązania reformulacji: oryginalne ograniczenie jest rozszerzone o człon kary kontrolujący najgorszą sumę odchyleń. Wynikiem jest większy, ale nadal możliwy do rozwiązania za pomocą MIP model.

4

Rozwiąż niezawodnie przeformułowany MIP za pomocą standardowego solwera typu branch-and-bound lub branch-and-cut (np. CPLEX, Gurobi, SCIP). Reformulacja zachowuje wymagania całkowitoliczbowości dla y. W przypadku dużych instancji, dekompozycja Bendersa lub metody płaszczyzn tnących mogą dekomponować problem.

5

Oceń niezawodne rozwiązanie poprzez: (a) obliczenie jego wartości funkcji celu dla parametrów nominalnych i najgorszych, (b) porównanie z rozwiązaniem programowania stochastycznego przy użyciu scenariuszy Monte Carlo oraz (c) raportowanie ceny niezawodności — dodatkowego kosztu poniesionego na ochronę przed niepewnością.

Częste pułapki

  • Wybór Gamma=0 (brak budżetu niepewności) odtwarza nominalny MIP i nie oferuje żadnej ochrony; zbyt duże Gamma prowadzi do nadmiernie konserwatywnych, niepraktycznych operacyjnie rozwiązań.
  • Traktowanie wszystkich parametrów jako jednocześnie niepewnych może sprawić, że reformulacja stanie się niemożliwa do rozwiązania — zidentyfikuj krytyczne niepewne parametry, aby chronić je selektywnie.
  • Ignorowanie struktury korelacji niepewności może skutkować nadmiernie pesymistycznym zbiorem niepewności; zbiory elipsoidalne są preferowane, gdy korelacje są znane.
  • Raportowanie tylko celu w najgorszym przypadku bez porównywania go z nominalnymi lub stochastycznymi punktami odniesienia daje niepełny obraz jakości rozwiązania.

Najczęściej zadawane pytania

Czym RMIP różni się od stochastycznego programowania mieszanego całkowitoliczbowego?

Stochastyczny MIP wykorzystuje rozkłady prawdopodobieństwa i optymalizuje oczekiwaną wydajność w próbkowanych scenariuszach, podczas gdy RMIP chroni przed najgorszym przypadkiem w ramach zbioru niepewności bez wymagania informacji o rozkładzie. RMIP daje jedno deterministyczne, niezawodne rozwiązanie; stochastyczny MIP daje politykę, która jest dobra średnio.

Czym jest „cena niezawodności” i jak duża jest zazwyczaj?

Cena niezawodności to procentowy wzrost wartości funkcji celu w porównaniu z optimum nominalnym (bez niepewności). Bertsimas i Sim pokazują, że rośnie ona w przybliżeniu liniowo z Gamma, ale pozostaje umiarkowana dla typowych wartości budżetu, często 5–15% w praktycznych zastosowaniach.

Czy RMIP może obsługiwać niepewne wartości prawej strony, a także niepewne współczynniki kosztów?

Tak. Niepewność w prawych stronach ograniczeń prowadzi do niezawodnych ograniczeń wykonalności, podczas gdy niepewność w współczynnikach funkcji celu wpływa na niezawodną optymalność. Oba mogą być obsługiwane jednocześnie w ramach budżetu niepewności, chociaż struktura reformulacji różni się.

Czy RMIP jest rozwiązywalny za pomocą standardowych solwerów MIP?

Dla zbioru budżetowego Bertsimasa-Sima, niezawodna reformulacja pozostaje MIP i może być rozwiązana bezpośrednio za pomocą solwerów takich jak CPLEX lub Gurobi. Elipsoidalne zbiory niepewności tworzą mieszane całkowitoliczbowe programy stożkowe drugiego rzędu (MISOCP), które są również obsługiwane przez nowoczesne solwery.

Kiedy powinienem preferować zbiór niepewności typu pudełkowego zamiast zbioru budżetu niepewności?

Zbiór pudełkowy chroni przed jednoczesnym odchyleniem wszystkich parametrów do ich ekstremów, co często jest nadmiernie konserwatywne. Zbiór budżetowy (Gamma) jest preferowany, gdy jednoczesne odchylenia wszystkich parametrów w najgorszym przypadku są mało prawdopodobne, ponieważ prowadzi to do mniej konserwatywnych i bardziej opłacalnych rozwiązań.

Pokrewne metody

Źródła

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.

    ISBN: 9780691143682
    Skopiowano.