Podręcznik

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.