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

Programowanie stochastyczne z ograniczeniami całkowitoliczbowymi — optymalizacja decyzji dyskretnych w warunkach niepewności

Autor metody
Dantzig, G. B.; Beale, E. M. L.
Rok
1955
Typ
Optimization under uncertainty with discrete decisions
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?

Programowanie stochastyczne z ograniczeniami całkowitoliczbowymi (SIP) to ramy optymalizacyjne łączące zmienne decyzyjne całkowitoliczbowe (dyskretne) z jawnym modelowaniem probabilistycznym niepewności.

Dąży ono do znalezienia najlepszej decyzji „tu i teraz”, która minimalizuje oczekiwany koszt (lub maksymalizuje oczekiwane korzyści) w całym rozkładzie przyszłych scenariuszy, uwzględniając fakt, że niektóre decyzje muszą zostać podjęte przed ujawnieniem niepewności.

Intuicja stojąca za metodą

Wiele rzeczywistych decyzji jest zarówno dyskretnych (zbudować obiekt czy nie; przydzielić pracownika czy nie), jak i niepewnych (popyt, koszty i ograniczenia nie są znane w momencie podejmowania decyzji). SIP radzi sobie z oboma wyzwaniami jednocześnie. Modeluje niepewną przyszłość jako zbiór scenariuszy z przypisanymi prawdopodobieństwami, a następnie znajduje rozwiązanie całkowitoliczbowe, które wypada najlepiej średnio — lub które zabezpiecza przed najgorszymi możliwymi wynikami. W przeciwieństwie do stochastycznego programowania liniowego, struktura dyskretna sprawia, że problem jest kombinatorycznie trudniejszy, ale uzyskane decyzje są bezpośrednio implementowalne bez zaokrąglania lub aproksymacji.

Historia

Programowanie stochastyczne wywodzi się od Dantzinga (1955) i Beale'a (1955), którzy niezależnie zaproponowali dwuetapowe modele rekursywne dla programów liniowych w warunkach niepewności. Rozszerzenie o ograniczenia całkowitoliczbowe pojawiło się wraz z rozwojem programowania całkowitoliczbowego w latach 60.–80. XX wieku. Podręcznik Birge'a i Louveaux z 1997 roku skodyfikował tę dziedzinę, a Kleywegt i in. (2002) ustanowili aproksymację średniej z próby jako standardowe podejście obliczeniowe dla wielkoskalowej stochastycznej optymalizacji dyskretnej.

Kiedy stosować

Używaj programowania stochastycznego z ograniczeniami całkowitoliczbowymi, gdy decyzje są z natury dyskretne (wybory binarne, alokacje w całych jednostkach, przypisania tras) i kluczowe parametry są niepewne w momencie podejmowania decyzji. Jest dobrze przystosowane do planowania zdolności produkcyjnych, projektowania sieci łańcucha dostaw, harmonogramowania przy niepewności popytu, dyspozycji energii i alokacji zasobów przy losowych uzyskach. NIE używaj go, gdy wszystkie zmienne są ciągłe (wystarczy stochastyczne programowanie liniowe), gdy niepewność jest znikoma lub w pełni obserwowalna przed podjęciem decyzji, gdy skala problemu sprawia, że enumeracja scenariuszy jest obliczeniowo niewykonalna bez infrastruktury dekompozycji, lub gdy istotny jest tylko pojedynczy scenariusz deterministyczny.

Ograniczenia i uwagi

  • Złożoność obliczeniowa rośnie szybko wraz z liczbą scenariuszy i zmiennych całkowitoliczbowych; duże instancje są NP-trudne.
  • Generowanie scenariuszy wymaga wiarygodnych rozkładów prawdopodobieństwa, które mogą być trudne do uzyskania lub oszacowania na podstawie ograniczonych danych.
  • Rozszerzenia wieloetapowe (więcej niż dwa etapy) napotykają wykładniczy wzrost drzew scenariuszy i rzadko są rozwiązywalne poza trzema etapami.
  • Wymagana jest biegłość w modelowaniu, aby poprawnie określić wykonalność rekursywną, ograniczenia nieantycyapacyjne i struktury kar.

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

Mocne strony

  • Jawnie modeluje niepewność zamiast używać estymacji punktowych, generując rozwiązania odporne na zrealizowane scenariusze.
  • Obsługuje decyzje dyskretne i binarne natywnie, dzięki czemu rozwiązania są bezpośrednio implementowalne bez zaokrąglania po fakcie.
  • Dwustopniowe ramy jasno oddzielają strategiczne decyzje pierwszego etapu od operacyjnych działań rekursywnych drugiego etapu.
  • Obsługuje bogate struktury rekursywne, w tym pozyskiwanie zasobów, koszty kar i harmonogramowanie korygujące.
  • Statystyczne granice jakości (poprzez SAA) pozwalają praktykom certyfikować bliskość optymalności z kwantyfikowaną pewnością.

Zastosowania

  • Projektowanie sieci łańcucha dostaw przy stochastycznym popycie i czasach realizacji
  • Planowanie rozbudowy produkcji energii elektrycznej przy niepewnym produkcji ze źródeł odnawialnych
  • Harmonogramowanie sal operacyjnych w szpitalach przy zmiennych czasach trwania procedur
  • Harmonogramowanie załóg lotniczych przy stochastycznych opóźnieniach lotów
  • Logistyka humanitarna — rozmieszczanie zapasów pomocy przed katastrofami
  • Optymalizacja portfela finansowego z dyskretnym wyborem aktywów i zwrotami opartymi na scenariuszach

Jak to działa

Jak to działa

1

Sformułuj problem pierwszego etapu: wybierz zmienne decyzyjne całkowitoliczbowe (lub mieszane całkowitoliczbowe) x przed ujawnieniem niepewności. Zdefiniuj cel, który obejmuje zarówno natychmiastowy koszt, jak i oczekiwany koszt rekursywny dla wszystkich scenariuszy. Tutaj określono ograniczenia łączące x z warunkami wykonalności.

Wzór
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]
2

Przedstaw niepewność poprzez skończony zbiór scenariuszy. Każdy scenariusz przypisuje określone wartości parametrom losowym (poziomy popytu, koszty, dostępność zasobów). Scenariusze mogą być generowane za pomocą próbkowania historycznego, losowań Monte Carlo z dopasowanych rozkładów lub zdefiniowanych przez ekspertów przypadków reprezentatywnych. Każdy scenariusz ma wagę prawdopodobieństwa, która sumuje się do jedności.

3

W standardowej dwuetapowej formulacji, po ustaleniu x i realizacji scenariusza xi, problem rekursywny (drugiego etapu) określa działania korygujące y. Problem rekursywny jest często programem liniowym lub całkowitoliczbowym. Pełny model minimalizuje c^T x plus oczekiwany koszt rekursywny E[Q(x, xi)].

Wzór
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)x
4

Rozwiąż podproblemy scenariuszowe, aby ocenić koszt rekursywny dla każdego scenariusza przy danym x. Techniki obejmują metodę podziału i ograniczeń (branch-and-bound), dekompozycję Bendersa, relaksację Lagrange'a i metodę aproksymacji średniej z próby (SAA). Dla dużych drzew scenariuszy algorytmy dekompozycji wykorzystują strukturę blokową między scenariuszami.

5

Agreguj wyniki podproblemów, aby oszacować oczekiwany koszt rekursywny. W SAA jest to średnia z S próbnych scenariuszy. Uzyskana aproksymacja zbiega do prawdziwej wartości oczekiwanej wraz ze wzrostem S. Statystyczne granice jakości rozwiązania można obliczyć na podstawie wariancji próby.

Wzór
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)
6

Zweryfikuj optymalność lub bliskość optymalności za pomocą luk optymalności, kryteriów zbieżności lub statystycznych przedziałów ufności z SAA. Jeśli luka nie jest akceptowalna, udoskonal zbiór scenariuszy, zwiększ wielkość próby lub zaostrz relaksacje. Zgłoś rozwiązanie pierwszego etapu x* i jego oczekiwany całkowity koszt.

Częste pułapki

  • Użycie zbyt małej liczby scenariuszy prowadzi do nadmiernie pewnych rozwiązań; użycie zbyt wielu sprawia, że problem jest obliczeniowo niewykonalny — równowagę osiąga się za pomocą diagnostyki zbieżności SAA.
  • Ignorowanie całkowitoliczbowości w drugim etapie, gdy jest ona faktycznie wymagana, prowadzi do optymistycznych szacunków kosztów i niewykonalnych działań rekursywnych.
  • Zakładanie niezależności scenariuszy, gdy parametry są skorelowane (np. skorelowany popyt i cena), wprowadza systematyczne obciążenie do estymacji kosztu oczekiwanego.
  • Zapomnienie o ograniczeniach nieantycyapacyjnych w problemach wieloetapowych pozwala modelowi na wykorzystanie przyszłych informacji, które nie byłyby dostępne w praktyce.

Najczęściej zadawane pytania

Czym programowanie stochastyczne z ograniczeniami całkowitoliczbowymi różni się od optymalizacji odpornej?

SIP minimalizuje oczekiwany koszt w zbiorze scenariuszy ważonych prawdopodobieństwem, akceptując, że niektóre scenariusze mogą prowadzić do wysokich kosztów, jeśli są mało prawdopodobne. Optymalizacja odporna minimalizuje koszt najgorszego przypadku w zbiorze niepewności, nie czyniąc żadnych założeń probabilistycznych. SIP wymaga rozkładu prawdopodobieństwa; optymalizacja odporna wymaga jedynie zbioru niepewności. SIP jest generalnie mniej konserwatywny, ale bardziej wymagający pod względem danych.

Ile scenariuszy jest potrzebnych w praktyce?

Zależy to od wymiaru problemu i pożądanej dokładności. Podejście aproksymacji średniej z próby (SAA) zapewnia statystyczne przedziały ufności dotyczące luki optymalności. Typowe badania stosowane wykorzystują od kilkudziesięciu do tysięcy scenariuszy; diagnostyka zbieżności (wariancja estymatora granicy) kieruje wyborem. Dla problemów strukturalnych techniki redukcji scenariuszy (np. Heitsch-Romisch) mogą znacznie zmniejszyć liczbę scenariuszy.

Czy programowanie stochastyczne z ograniczeniami całkowitoliczbowymi może obsługiwać więcej niż dwa etapy?

Tak, ale wieloetapowe SIP jest znacznie trudniejsze. Drzewo scenariuszy rośnie wykładniczo wraz z liczbą etapów, a ograniczenia nieantycyapacyjne muszą być egzekwowane w każdym węźle. W praktyce modele trójstopniowe są normą dla rozwiązywalnych zastosowań; poza tym zazwyczaj wymagane są aproksymacje, takie jak horyzont kroczący lub redukcja drzewa scenariuszy.

Jakie oprogramowanie potrafi rozwiązywać modele programowania stochastycznego z ograniczeniami całkowitoliczbowymi?

Typowe solvery obejmują CPLEX i Gurobi (za pośrednictwem algebraicznych języków modelowania, takich jak AMPL, JuMP w Julia lub PuLP/Pyomo w Pythonie), które obsługują dekompozycję scenariuszy. Specjalistyczne frameworki programowania stochastycznego obejmują PySP (Python), solvery w formacie SMPS oraz pakiet Julia StochasticPrograms.jl, który implementuje SAA i progresywne ukrywanie (progressive hedging).

Czy programowanie stochastyczne z ograniczeniami całkowitoliczbowymi to to samo co stochastyczne programowanie mieszane całkowitoliczbowe?

Programowanie stochastyczne z ograniczeniami całkowitoliczbowymi jest szerszą klasą; stochastyczne programowanie mieszane całkowitoliczbowe (SMIP) odnosi się konkretnie do modeli, w których niektóre zmienne są ciągłe, a inne całkowitoliczbowe na jednym lub obu etapach. SMIP jest najbardziej ogólną i najczęściej spotykaną formą w praktyce.

Pokrewne metody

Źródła

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 978-1-4614-0237-4
    Skopiowano.
  2. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.

    Otwórz odnośnik DOI
    Skopiowano.