Podręcznik

Różnorodność problemów dyskretnych jest w zasadzie nieskończona. Wynika ona m.in. z niezwykle szerokiej gamy dziedzin, w której problemy optymalizacji dyskretnej mają zastosowanie. Jednocześnie, na najbardziej ogólnym poziomie problemy te łączy podobny cel: zwiększenie efektywności przy zachowaniu wymagań i ograniczeń na zasoby. Co więcej, często okazuje się, że problemy z różnych dziedzin wykorzystują podobne zestawy zmiennych decyzyjnych i ograniczeń, czyli dzielą podobną strukturę. Pomocne jest  zatem przestudiowanie reprezentatywnych przykładów, które mogą służyć jako paradygmaty podczas modelowania i rozwiązywania innych problemów o podobnej strukturze.

Przypomnijmy przy tym, że w przypadku rozwiązywania problemów dyskretnych gotowymi solwerami duże znaczenie może mieć sformułowanie modelu, w szczególności nierzadkie są przypadki niepotrzebnie złożonego sformułowania, wprowadzającego np. nieliniowości do modelu. Tym samym, zapoznanie się z klasycznymi problemami pomoże wypracować dobre praktyki tworzenia modeli optymalizacyjnych programowania matematycznego.

Klasy problemów

Wiele problemów dyskretnych może być przedstawianych jako zadania wyznaczania przepływów w sieci, należą do nich klasyczne problemy grafowe, takie jak:

•  Najkrótsze i najtańsze ścieżki, przepływy w grafach,
• Cykl komiwojażera: Traveling Salesperson Problem (TSP),
• Przydziały i skojarzenia: Assignment Problem,
• Minimalne drzewo rozpinające: Minimum spanning tree.

W tym rozdziale przedstawiamy jedynie kilka wybranych, klasycznych problemów alokacji zasobów.

Problem plecakowy: Knapsack problem

Problem plecakowy/ zadanie załadunku polega na jak najlepszym wykorzystaniu zasobu (plecaka), w którym należy upakować jak najwięcej przedmiotów. 

Oznaczenia:

• $i\in N$ zbiór typów przedmiotów o wartości $w_i$ i wielkości $a_i$,

• $p$ pojemność plecaka (zasobu)
  

• $x_i$ zmienna decyzyjna ile przedmiotów typu $i$ zapakować.

Funkcja celu: $\max\sum_i w_i x_i$

Ograniczenia dotyczą dostępności zasobu, oraz przedmiotów:

$\begin{matrix} &&\sum_i a_i x_i\leq p,\\ && x_i \subset C,\; \forall i\end{matrix}$

Warianty problemu plecakowego

Problem typu plecakowego ma szerokie zastosowania w różnych dziedzinach, np. do tej kategorii zaliczamy problemy inwestycyjne i zadania alokacjai budżetu. Dodatkowe uwarunkowania prowadzą do wariantów podstawowego problemu, wyróżniamy np.:

•  0-1 Knapsack - tylko po jednej sztuce każdego towaru jest dostępne,
• Bounded knapsack - dostępna jest ograniczona liczba sztuk każdego towaru,
• Change-making - pojemność plecaka musi być w pełni wykorzystana (czyli ograniczenia na zasób w postaci równości),
• Multiple Knapsack - wiele różnych plecaków, inaczej problemy typu bin-packing, które dalej mogą być rozważane wraz z ograniczeniami kolejnościowymi, oknami czasowymi, itd.

Problem bin-packing

Problemy pakowania  (i rozkroju, czyli w wariancie Cutting stock problem) najczęściej skupiają się na wykorzystaniu jak najmniejszej liczby zasobów.

Oznaczenia:

• $p_j$ pojemność pojemnika $j\in M$,

• $x_{ij}$ zmienna decyzyjna ile przedmiotów typu $i$ zapakować do pojemnika $j$,

• $y_{j}$ zmienna decyzyjna czy wykorzystać pojemnik  $j$.
  

Funkcja celu: $\min\sum_j y_j$

Ograniczenia:

$\begin{matrix} &&\sum_i a_i x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset C,\; \forall i,j\end{matrix}$

Przydział zadań do procesorów/dostawców do odbiorców

Szeroka klasa problemów przydziału może być postrzegana jako wariant bin-packingu.  W problemie takim zasoby $j\in M$ to np. maszyny, dostawcy, itp. Natomiast zbiór $i\in N$ reprezentuje zbiór zdań do realizacji/obsłużenia.

Oznaczenia:

• $a_{i}$ jest zapotrzebowaniem zadania $i$, w wersji $a_{ij}$ zróżnicowanym ze względu na zasoby, np. odpowiada czasowi wykonania zadania $i$ na maszynie $j$,
• $f_{ij}$ jest kosztem wykonania zadania $i$ na maszynie $j$.
  

Funkcja celu minimalizuje koszty: $\min\sum_{ij}f_{ij} x_{ij}$

Przy ograniczeniach jak w zadaniu bin-packingu, przy czym o ile w zadaniu nie ma kosztów stałych powiązanych z wykorzystaniem maszyny to nie podrzebujemy zmiennej binarnej $y_j$:

$\begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix}$

Problemy lokalizacyjne/dystrybucyjne

Klasycznym rozszerzenime problemu przydziału zadań do procesorów jest dodatkowe uwzględnie stałego kosztu użycia procesora. Problem tego typu jest określany jako problem lokalizacyjny, gdyż ma naturalne odzwierciedlenie w sytuacji wyboru punktów obsługi (klientów, pacjentów, mieszkańców, etc.). Problem ten posłuży nam do omówienia sposobu implementacji modeli w środowisku IBM Ilog Cplex w kolejnych rozdziałach.

Oznaczenia dodatkowe:

• $c_{j}$ jest stałym kosztem wykorzystania zasobu $j$ (ustanowienia zasobu w lokalizacji  $j$)

Przy ograniczeniach jak w zadaniu bin-packingu:

$\begin{matrix} &&\sum_{ij} a_{ij} x_{ij}\leq p_jy_j\;\;\;\forall j\in M,\\ && \sum_jx_{ij}=1\;\forall i\in N\\ && x_{ij} \subset \{0,1\},\; \forall i,j\end{matrix}$

Rozważmy problem lokalizacji, którego opis oparty jest na materiale szkoleniowym [CPLEX Optimization Studio Fundamentals Tutorial](https://www.ibm.com/cloud/garage/dte/tutorial/cplex-optimization-studio-fundamentals-tutorial).

Opis. Firma rozważa kilka lokalizacji pod budowę magazynów, które wspomagałyby obsługę jej sklepów. Dany jest stały koszt otwarcia  magazynu, a także koszt związany z zaopatrzeniem sklepu z każdej z potencjalnych lokalizacji. Warunki:

• Każdy sklep może być zaopatrywany tylko przez jeden magazyn.
• W każdej lokalizacji można postawić magazyn o określonej pojemności, wskazującej ile maksymalnie sklepów możne on obsłużyć.

Decyzje. Problemem jest podjęcie decyzji, ile magazynów i w których lokalizacjach otworzyć, aby jak najtaniej obsłużyć wszystkie sklepy.

Przykładową ilustrację zadania przedstawia poniższy rysunek z artykułu J. de Armas, et. al (2017) 'Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic', Journal of the Operational Research Society, 68:10, 1161-1176, DOI: 10.1057/s41274-016-0155-6

Dla ustalenia uwagi, może przyjąć następujące dane dla naszego problemu.

• Jest 5 potencjalnych lokalizacji magazynów -  Bonn, Bordeaux, London, Paris, Rome oraz 10 sklepów.
• Koszty stałe otwarcia magazynu są takie same dla wszystkich lokacji i wynoszą 30.
• Poniższa tabela zawiera dopuszczalne pojemności magazynów i koszty zaopatrzenia sklepów.
  

Mogą być różne metody rozwiązywania przedstawionego problemu lokalizacji, który należy do jednego z klasycznych zadań optymalizacji. Jedną z metod jest sformułowanie problemu w postaci zadania programowania matematycznego i rozwiązanie przy użyciu solwera, co prezentujemy w tym rozdziale.

Formalnie, każdy model programowania matematycnego składa się z 3 części: oznaczeń, funkcji celu i ograniczeń. Zaczynamy od oznaczeń, które również składają się z 3 części: zbiorów, parametrów i zmiennych decyzyjnych. Parametry to wszelkie wartości liczbowe pojawiające się w sformułowaniu konkretnego przypadku liczbowego, tzw. case study. W naszym zadaniu najważniejsze dane zawiera przedstawiona powyżej tabela. Warto zwrócić uwagę, że wszelkie tabele pojawiające się w opisie zadania wskazują w naturalny sposób kandydatów do zbiorów: najczęściej znajdują się w pierwszej kolumnie, oraz/lub w pierwszym wierszu. W naszym przykładzie, dla danych przedstawionych w tabeli powyżej widzimy zbiór lokalizacji, oraz zbiór sklepów. W komórkach tabeli są parametry opisujące poszczególne lokalizacje oraz pary lokalizacja-sklep.

Oznaczenia w analizowanym problemie:

Zbiory:

•  $w\in W$ lokalizacje dla magazynów (warehouses)
• $s\in S$ sklepy (stores)

Parametry:

• $FC$ stały koszt otwarcia magazynu (fixed cost)
  
• $SC_{sw}$ koszt zaopatrzenia sklepu $s$ z magazynu $w$ (supply cost)
  
• $C_w$ max. pojemność magazynu $w$ (capacity)
  

Zmienne decyzyjne:

• $x_{sw}$ czy sklep $s$ zaopatrzany z magazynu $w$
• $y_{w}$ czy magazyn $w$ otwarty

Funkcja celu:

Kolejny element to zdefiniowanie funkcji celu, pozwalającej na ocenę rozwiązania, czyli konkretnych wartości zmiennych decyzyjnych. W rozważanym przykładzie chcemy  jak najtaniej otwierać magazyny, oraz przydzielać do nich obsługiwane sklepy, czyli w funkcji celu minimalizujemy koszty:

minCost = $\min \sum_w(FC\cdot y_w+\sum_s SC_{sw}\cdot x_{sw})$${\displaystyle {}_{}}$

Ograniczenia:

Ostatni element modelu, to wskazanie zależności, które muszą spełniać zmienne decyzyjne, aby rozwiązanie było dopuszczalne. W rozważanym problemie opisano dwa warunki, które przekładają się na matematyczny zapis trzech rodzajów ograniczeń:

$\min \; c^T x$, p.o.: $x\in S$, tj.:

$Ax\geq b$

$\displaystyle x\in \mathcal{C}^+.$

Metoda podziału i oszacowań zakłada:

• przegląd obszaru rozwiązań dopuszczalnych $S$ poprzez iteracyjny podział (branch) tego obszaru, czyli wydzielanie podproblemów dzięki dodaniu ograniczeń odcinających część rozwiązań,
• iteracyjne szacowanie (bound) rozwiązania w każdym podproblemie w sposób przybliżony, niedokładny, co uzyskiwane jest dzięki relaksacji podproblemu - najczęściej jest stosowana relaksacja warunku całkowitoliczbowości, ale też np. relaksacja Lagrange'a, i in..

Podproblemy (podziały) są organizowane w postaci drzewa. Metoda B&B pozwala na systematyczne i efektywne zawężanie zakresu dla optimum globalnego, gdyż w każdej iteracji wyznaczane jest:

• dolne oszacowanie LB (Lower Bound), czyli wartości f. celu podproblemu wskazująca na jego potencjalną atrakcyjność i potrzebę dalszej eksploracji (lub pominięcia),
• górne oszacowanie UB (Upper Bound), czyli najlepsza do-tej-pory wartość f. celu podproblemu, w którym osiągnięto rozwiązanie globalnie dopuszczalne, tzw. incumbent solution (np. całkowitoliczbowe, lub ogólnie, takie że $x\in S$).

W pojedynczej iteracji znajdujemy się w konkretnym węźle drzewa B&B, gdzie rozwiązujemy zrelaksowane zadanie z dodatkowym ograniczeniem obszaru dopuszczalnego po to, aby uzyskać lokalne oszacowanie LB. Analizując LB oraz UB mamy dwie możliwości:

• podzielenie węzła, czyli dodanie ograniczeń, gdy aktualne, lokalne LB < globalne UB (jest szansa, że w danym obszarze znajdziemy lepsze rozwiązanie od tego, które mamy do tej pory), a następnie wybór części (węzła) do eksploracji;
• zamknięcie węzła i powrót poziom wyżej, co następuje w 3 przypadkach:
1. rozwiązanie sprzeczne -- ograniczenie w tym węźle powoduje, że obszar dopuszczalny staje się pusty;
2. rozwiązanie całkowitoliczbowe -- staje się nowym UB jeśli wartość lokalnego LB< globalne UB dotychczasowe;
3.  aktualne, lokalne LB > globalne UB -- zrelaksowane rozwiązanie w podproblemie gorsze niż najlepsze rozwiązanie do-tej-pory (nie ma szans, aby w danym obszarze znaleźć lepsze rozwiązanie od tego, które mamy do tej pory).

Zależności między LB i UB przedstawia poniższy rysunek.

1. (Inicjalizacja): Przyjmij $L$={$\mathrm{IP}^0$}, UB=$\infty$, $\mathrm{LB}_0=-\infty$.
2. (Zakończenie): Jeżeli $L$={$\emptyset$}, to $\hat{x}$ dla którego osiągnięto UB jest rozwiązaniem optymalnym. Jeśli nie ma takiego rozwiązania, tj. UB=$\infty$, to problem $\mathrm{IP}$ jest sprzeczny lub nieograniczony.
3. (Wybór problemu i relaksacja): Wybierz oraz usuń z $L$ problem $\mathrm{IP}^i$, rozwiąż jego relaksację. Jeśli rozwiązanie istnieje, przyjmij za $\mathrm{LB}_{i}$ wartość f. celu, oraz za $x_i$ wartość zmiennych decyzyjnych. W przeciwnym przypadku $\mathrm{LB}_{i}=\infty$.
4. (Zamykanie wierzchołka):
   1. Jeżeli $\mathrm{LB}_{i}\geq$UB idź do Kroku 2.
   2. Jeżeli $x_i\in S$ (rozw. całkowitoliczbowe) zaktualizuj UB=$\mathrm{LB}_{i}$ i $\hat{x}=x_i$, oraz usuń z $L$ te problemy $\mathrm{IP}^k$, dla których $\mathrm{LB}_k\geq$UB. Idź do Kroku 2.
5. (Podział wierzchołka): Przyjmij $\{S^{ij}\}_{j=1}^{k}$ jako podział zbioru $S^i$ problemu $\mathrm{IP}^i$ na $k$ rozłącznych podzbiorów. Dodaj do $L$ wszystkie problemy $\{\mathrm{IP}^{ij}\}_{j=1}^{k}$, gdzie $\mathrm{IP}^{ij}$ to problem $\mathrm{IP}^i$ z obszarem dopuszczalnym ograniczonym do $S^{ij}$, oraz $\mathrm{LB}_{ij}=\mathrm{LB}_{i}$. Idź do Kroku 2.

Kwestie wymagające inteligentnego podjęcia decyzji:

• pkt. 3 - wybór problemu (wierzchołka do eksploracji)
• pkt. 5 - sposób podziału problemu oraz
• pkt. 5 - wybór zmiennej do ograniczenia; Plus wybór sposobu relaksacji.

Funkcją szacującą (ang. bounding function) nazywamy metodę pozwalającą wyznaczyć jakość rozwiązań w podproblemie zrelaksowanym.

Liczba wierzchołków drzewa B&B może rosnąć wykładniczo, dlatego ważne jest:

• Wyznaczenie oszacowania LB możliwie dużej wartości, blisko wartości optymalnej co pozwala na szybkie zamykanie podproblemów;
• Wyznaczenie oszacowania możliwie mało czasochłonne;
• Idealnie jeśli w podproblemie oprócz oszacowania LB potrafimy stosunkowo łatwo wyznaczyć rozwiązanie dopuszczalne;
• Dwie ogólne metody szacowania optymalnej f. celu:
  1. relaksacja części ograniczeń, optymalizacja w łatwiejszym (szerszym) zbiorze $S^R$, takim że  $S\subseteq S^R$;
  2. modyfikacja f. celu tak, że  $g(x)≤f(x)$, np. poprzez zastąpienie sumą kosztów implikowanych aktualnym ograniczeniem na zmienne.
  • Relaksacja Lagrange’a: połączenie tych strategii – silne, ale czasochłonne,
  • Najczęściej stosowana relaksacja liniowa, czyli odrzucenie warunku całkowitoliczbowości.

Wyróżniamy następujące reguły podziału podproblemów.

Podział na 2 części (dytochomiczny)

• przy stosowaniu relaksacji liniowej wprowadzane są dwa ograniczenia na zmienną $x_i$, której wartość nie jest całkowitoliczbowa: jeśli zapiszemy wartość $x_i=n+d$, gdzie $d$ jest częścią ułamkową, to warunki podziału mają postać:
  • $x_i \leq n$
  • $x_i \geq n+1$
• generalizacja podziału, tzw. ograniczenie GUB (generalized upper bound): w zadaniach przydziału, w których wymagamy aby tylko jedna zmienna miała wartość niezerową, czyli z ograniczeniami postaci $\sum_i x_i = 1$ można dzielić węzeł, ze względu na sumaryczną wartość zmiennych, których wartości są zbliżone, czyli dzielimy $S = S_1 \cup S_2$ i wymagamy aby $\sum_{i\in S_1} x_i =0$ lub $\sum_{i\in S_2} x_i =0$ (w orginalnym zbiorze $S$ te dwie sumy są ułamkowe i mają zbliżone wartości)

• wg największej/najmniejszej niedopuszczalności - wybierana zmienna, której wartość jest najdalej/najbliżej od jej wartości zaokrąglenia
• na podstawie szacowanej wartości zmiennej: różne sposoby szacowania pogorszenia funkcji celu, aby ocenić opłacalność wymuszenia ograniczenia danej zmiennej
• wyliczanie kar (penalty) na podstawie kosztów zredukowanych zmiennej, dla której sprawdzamy koszty wyjścia z bazy (w metodzie dual simplex),
• szacowanie pseudokosztów zredukowanych na podstawie wartości f. celu, w której zmienna wymuszona na wartość całkowitoliczbową,
• szacowanie pseudocen dualnych - j.w. tylko w odniesieniu do cen dualnych, a nie kosztów zredukowanych,
• silny podział (strong branching) - wyliczenie wartości f. celu w kilku iteracjach algorytmu simplex, przy ustalonej (całkowitoliczbowej) wartości zmiennej;
• użycie priorytetów podanych przez użytkownika.

Użycie hiperpłaszczyzn (branch and cut)

• Na podstawie znajomości struktury problemu dodajemy odcięcia angażujące większą liczbę zmiennych, uzyskane np. poprzez agregację niektórych ograniczeń.

Podział na wiele części (politochomiczny)

• Przykładowo, w problemie komiwojażera (TSP), dla relaksacji opartej na drzewie rozpinającym możemy wybierać wiele restrykcji dla konkretnego podproblemu, gdyż sprowadzają się one do usunięcia konkretnych krawędzi z aktualnej drogi TSP; przykład można znaleźć w książce W. L. Winstona „Operations research - Applications and Algorithms" Thomson Learning (2004);
• priorytet zmiennej do wyboru na podst. znajomości problemu: w najprostszym przypadku wg wektora cen.

Relaksacja Lagrange'a (Lagrangian Relaxation) to jedna z najważniejszych technik relaksacji, czyli metod aproksymacji trudnego zadania optymalizacji przy pomocy zadania prostszego. Rozwiązanie prostszego, zrelaksowanego problemu daje przybliżenie, aproksymację optymalnego rozwiązania oryginalnego problemu. Dla zadań optymalizacji dyskretnej najprostszą relaksacją jest odrzucenie warunku całkowitoliczbowości (stosowane np. w metodzie podziału i oszacowań), czyli tzw. relaksacja liniowa. Stosowanie relaksacji Lagrange'a daje lepsze efekty, w sensie wartości funkcji celu.

Zapiszmy problem minimalizacji jako zadanie: 

$\min \; c^T x$, p.o.:

$f(x)\geq d$

$g(x)\leq b$

$\displaystyle x\in \mathcal{C}^+,$

gdzie zbiór ograniczeń definiowanych funkcją $f(x)$ ma stosunkowo prostą strukturę i można je uznać za łatwe, natomiast zbiór ograniczeń $g(x)$ jest uznawany za trudny. Wtedy uproszczenie problemu, czyli jego relaksacja będzie polegać na pominięciu trudnych ograniczeń. Dla zadania minimalizacji, rozwiązanie problemu zrelaksowanego pozwala uzyskać oszacowanie dolne  (lower bound).

W relaksacji Lagrange‘a nie pomija się całkowicie ograniczeń, lecz zamiast tego tworzy się tzw. funkcję Lagrange‘a dodając do funkcji celu liniową funkcję ”kary” za ewentualne przekroczenie ograniczeń. Uzyskana dzięki temu relaksacja jest znacznie silniejsza.

 Wektor mnożników Lagrange'a $\lambda$ ma wyceniać wartości pominiętych ograniczeń, czyli musi być określony w taki sposób, że wartości funkcji Lagrange'a są zgodne z wartościami funkcji celu pierwotnego problemu. Można też wykazać silny związek między mnożnikami Lagrange'a a zmiennymi zadania dualnego, wykracza to jednak poza zakres tego wykładu.

Mnożniki Lagrange'a należy dobrać w taki sposób, aby oszacowanie dolne było jak najlepsze, czyli jak największe. Definiuje się zatem tzw. funkcję prymalną Lagrange'a , która dla dowolnie dużych mnożników λ osiąga wartość pierwotnej funkcji celu:

gdzie jest zbiorem rozszerzonym, uzyskanym przez relaksację ograniczeń wprowadzonych do funkcji Lagrange'a.

Odpowiadającą funkcji prymalnej Lagrange'a funkcję dualną możemy zapisać definiując dualną funkcję Lagrange'a :

• dla ograniczeń równościowych, czyli np.
• dla ograniczeń typu ≤ , czyli np.
• dla ograniczeń typu ≥, czyli np. .

Optymalną wartość funkcji Lagrange'a, odpowiadającą problemowi optymalizaci zapiszemy zatem jako:

Dla dowolnej wartości λ wartość funkcji jest relaksacją pierwotnego problemu optymalizacji, pozwala na oszacowanie od dołu minimalizowanej funkcji celu:

i w szczególności .

Dla dowolnej pary zachodzi . W punkcie optymalnym różnica między wartością dualną i prymalną jest najmniejsza i wynosi 0. W ogólnym przypadku zadań dyskretnych różnica

nie zawsze wynosi 0 i mówimy wtedy o odstępie dualności. Odstęp dualności (duality gap) jest miarą siły relaksacji Lagrange'a.

• Można udowodnić, że wartość funkcji nie zmieni się, jeżeli dopuszczalny zbiór X problemu pierwotnego zastąpimy jego uwypukleniem . Zauważmy, że , co jest zgodne z obserwacją o przewadze relaksacji Lagrange'a nad relaksacją liniową.
• Funkcja jest wklęsła względem λ, czyli wystarczy znaleźć maksimum lokalne i można je wyznaczyć metodami subgradientowymi.
• Rozwiązanie optymalne funkcji spełnia warunek komplementarności, czyli jeśli pewne to odpowiadające im ograniczenia są spełnione.
• Do wyznaczenia oszacowania wystaczy znaleźć rozwiązanie dopuszczalne zadania dualnego, nie trzeb szukać jego optimum.

jest realizowane 

,

gdzie jest dobraną arbitralnie wielkością startową, a dualna funkcja Lagrange'a ma postać:  (relaksowane ograniczenie ma postać $Ax\geq b$  ).

Rozmiar kroku (współczynnik przesunięcie) wyznacza się ze wzoru:

gdzie współczynnik τ zawiera się w przedziale a jest górnym oszacowaniem . Wyznaczenie dobrego górnego oszacowania może być trudne przy dużych i złożonych problemach optymalizacji.

Formalna konstrukcja algorytmu wyznaczania mnożników Lagrange'a:

• Krok 0. Dane: zbiór otrzymany ze zbioru X przez relaksację ograniczeń, wprowadzonych do funkcji Lagrange'a. Parametry:
  • maksymalna liczba iteracji
  • maksymalny odstęp dualności
  • początkowe wartości mnożników Lagrange'a
  • oszacowanie od góry dualnej funkcji Lagrange'a
  • metoda aktualizacji mnożników
  • k=0
• Krok 1. Oblicz oraz rozwiązując zrelaksowane zadanie Lagrange'a
• Krok 2. Sprawdź, czy jest prymalnie dopuszczalne, jeśli tak, oblicz . Jeśli to STOP
• Krok 3. Wyznacz rozmiar kroku , jeśli to STOP
• Krok 4. Zaktualizuj , , jeśli to STOP, w p.p. wróć do kroku 1

STOP.

Problemy z metodą RL

Podczas rozwiązywania dużych i złożonych problemów MILP, nawet zrelaksowany problem z kroku 1 może być trudny do rozwiązania. Do tego kierunki aktualizacji mnożników mogą się bardzo zmieniać co przejawia się niestabilnym zygzakowaniem mnożników. Ostatnia kwestia, to niedopuszczalność rozwiązania uzyskanego w wyniku rozwiązania zadania zrelaksowanego, gdyż może ono przekraczać ograniczenia zrelaksowane.

Znajdowanie rozwiązań dopuszczalnych

Obszary badań

• algorytmy wyznaczania parametrów początkowych ()
• algorytmy aktualizacji mnożników
• algorytmy wyznaczania rozwiązania dopuszczalnego
• algorytmy specjalizowane dla konkretnych problemów.

W tym rozdziale pokażemy możliwości wykorzystania dekomponowalnej struktury zadania lokalizacji, stosując zamiast relaksacji techniki restrykcji. Restrykcja to technika polegająca na dodatkowym ograniczaniu zbioru dopuszczalnego problemu optymalizacji. W omawianej we wcześniejszych rozdziałach metodzie podziału i oszacowań restrykcja była wykorzystywana do wydzielania części obszaru dopuszczalnego poprzez narzucenie ograniczeń typu nierównościowego na zmienne. W metodzie opracowanej przez Bendersa w 1962r. restrykcja polega na narzuceniu konkretnych wartości wybranym zmiennym całkowitoliczbowym, podczas gdy pozostałe zmienne są optymalizowane. Metoda Bendersa ma zatem zastosowanie do rozwiązywania tylko pewnych klas problemów optymalizacji, dla których w możliwy jest rozdział zmiennych, w szczególności prowadzący do wyodrębnienia zadania programowania liniowego oraz zadania programowania dyskretnego, które jest łatwiejsze do rozwiązywania od pierwotnego problemu dyskretno-ciągłego.

Przypomnijmy, ze w zadaniu lokalizacji rozważanym w poprzednim podrozdziale poświęconym relaksacji Lagrange'a problem pierwotny polega na określeniu, w których miastach otworzyć magazyny (zmienna binarna $y_j$) oraz w jakich proporcjach zaspokoić zapotrzebowanie klientów w miastach $i$ zaopatrywanych przez magazyny $j$ (zmienna ciągła z zakresu $0\leq x_{ij}\leq 1$).  Dla uproszczenia, analizujemy łatwieszą wersję problemu, w którym pomijamy ograniczone pojemności magazynów.

Sformułowanie matematyczne problemu pierwotnego P:

$P=\min \sum_{ij} c_{ij}x_{ij} +\sum_i f_iy_i$
p.o.:
(1) $\sum_i x_{ij}= 1\;\;\;\forall j\in \mathrm{cities}$
(2) $x_{ij}\leq y_i\;\;\;\forall i,j\in \mathrm{cities}$
(3) $x_{ij}\geq 0,\;\; y_i\in\{0,1\}\;\;\;\forall i,j\in \mathrm{cities}.$

Zdefiniujmy teraz problem operujący tylko na zmiennych ciągłych $0\leq x_{ij}\leq 1$, w którym $y_j$ jest traktowane jako parametr - zostało poddane restrykcji. Przyjmując, że wartości wektora  $y_j$ są ustalone, restrykcja $PX(y)$ zadania (P) jest podproblemem sparametryzowanym przez y. W takiej sytuacji $PX(y)$ jest zadaniem liniowym względem zmiennej x o następującej postaci:

$PX(y)= \min \sum_{ij} c_{ij}x_{ij}$
p.o.:
(4) $\sum_i x_{ij}= 1\;\;\;\forall j\in \mathrm{cities},\;\;\; \perp \lambda_j$
(5) $x_{ij}\leq y_i\;\;\;\forall i,j\in \mathrm{cities}, \;\;\;\perp v_{ij}$
(6) $x_{ij}\geq 0,\;\; \;\;\forall i,j\in \mathrm{cities}.$

W powyższym sformułowaniu oznaczyliśmy też zmienne dualne do ograniczeń (4) i (5), które będą wykorzystane w dalszej analizie metody Bendersa. Przypomnijmy, że sformułowanie dualne można rozważać tylko dla problemów ze zmiennymi ciągłymi - a taki właśnie jest problem $PX(y)$. Zauważmy przy okazji, że problem $PX(y)$ może być zdekomponowany na $j$ niezależnych podproblemów optymalizacji, podobnie niezależnie można określać odpowiednie zmienne dualne . Podproblem $PX^j(y)$:

$PX^j(y)= \min \sum_{i} c_{ij}x_{ij}$
p.o.:
(7) $\sum_i x_{ij}= 1,,\;\;\; \perp \lambda_j$
(8) $x_{ij}\leq y_i\;\;\;\forall i\in \mathrm{cities},\;\;\;\perp v_{ij}$
(9) $x_{ij}\geq 0,\;\; \;\;\forall i\in \mathrm{cities}.$

W metodzie dekompozycji Bendersa kolejnym elementem schematu postępowania jest sformułowanie dualne zadania $PX(y)$ określane jako problem D1. Skorzystamy z możliwości dekompozycji zadania $PX(y)$ na podproblemy i dla ułatwienia rozważań sformułujemy podproblem  $D1^j(y)$:

$D1^j(y)= \max \lambda_j+\sum_{i} y_iv_{ij}$
p.o.:
(10) $\lambda_j+v_{ij} \leq c_{ij},,\;\;\; \forall i\in \mathrm{cities}$
(11) $\lambda_j \mathrm{nieogr.},\;\;\; v_{ij}\geq 0$.

Zmienna dualna $\lambda_j$ w zadaniu $D1^j(y)$ jest nieograniczonego znaku, przy czym musi być zawsze niezerowa, tj. musi być zmienną bazową (każde miasto musi być zaopatrzone). Ze względu na maksymalizację, oraz ograniczenie (10) $\lambda_j$ będzie przybierać najniższą z wartości  $c_{ij}$, dla których  $y_{i}=0$. Natomiast w pozostałych przypadkach, z tego względu że w bazie nie może być dodatkowych zmiennych $v_{ij}$ (lub zmiennych dopełniających) szczególna postać tego zadania pozwala wyznaczyć rozwiązania zmiennych dualnych jako:

$\lambda_j = c_{kj},\;\; v_{ij} = ((c_{1j}-c_{kj})^+, (c_{2j}-c_{kj})^+,\ldots, (c_{nj}-c_{kj})^+)$.

Stąd:

$\hat{r}^j = \max_{k\in \mathrm{cities}} [c_{kj}+ \sum_{i \in \mathrm{cities}}y_i(c_{ij}-c_{kj})^+]$.

Najważniejszą cechą zadania dualnego w metodzie Bendersa jest to, że jego zbiór rozwiązań dopuszczalnych nie zależy od wyboru $y$. Dzieje się tak, ponieważ ustalony $y$ jest pomijany w funkcji celu zadania pierwotnego, a jak pamiętamy, w ograniczeniach zadania dualnego wykorzystywane są jedynie współczynniki funkcji celu zadania prymalnego. Niezależność zbioru dopuszczalnego $D1(y)$ od wektora $y$ pozwala na rozważanie wyłącznie punktów wierzchołkowych tego zbioru, gdyż to w jednym z nich znajduje się optimum, którego wartość zależy od $y$.  To pozwala przekształcić problem P do równoważnego zadania D2. W rozważanym tu problemie lokalizacji jest on następującej postaci. Problem $D2$:

$D2= \max \sum_i f_iy_i   +\sum_{j} r_j$
p.o.:
(12) $r_j\leq  -c_{kj}+\sum_{i \in \mathrm{cities}}y_i(c_{kj}-c_{ij})^+,\;\;\; \forall k,j\in \mathrm{cities}$

(13) $\sum_i y_i\geq 1,$

(13) $r_j \in R\;\;\; y_{j}\in\{0,1\}\$.

Bezpośrednie rozwiązywanie zadania D2 jest na ogół niepraktyczne, gdyż wymaga wyznaczenia wszystkich punktów wierzchołkowych zbioru dualnego, co może być szczególnie kłopotliwe w przypadku dużej liczby wierzchołków. Dlatego Benders opracował iteracyjną procedurę, która pozwala na wyznaczenie optymalnego wierzchołka zbioru dualnego zazwyczaj w niewielkiej liczbie iteracji.

Bendersa może być szczególnie efektywna w przypadku, gdy struktura macierzy ograniczeń jest blokowo-diagonalna z wstęgą pionową, jak pokazano na poniższym rysunku.

Innym przykładem możliwości zastosowania metody dekompozycji Bendersa jest sytuacja, gdy funkcje powiązane ze zmienną $y$ mają szczególną strukturę, np. wynikającą z przepływu w sieciach.