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.