3. Techniki restrykcyjne i relaksacyjne

3.2. Restrykcja - dekompozycja Bendersa

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 restrykcjiPrzyjmują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 D1Tak. 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.

Formalna konstrukcja algorytmu Bendersa:

  • Krok 0. Wyznacz wartość wektora zmiennych dualnych v^0 jako dowolne rozwiązanie dopuszczalne problemu dualnego D1(y) - uwaga, nie musi to być punkt wierzchołkowy zbioru dopuszczalnego. Jeżeli rozwiązanie dopuszczalne nie istnieje, to STOP. W p. p. przyjmij k = 1 i idź do kroku 1.
  • Krok 1. Rozwiąż zadanie zrelaksowane P^k, tzn. zadanie D2, w którym występuje jedynie k ograniczeń. W wyniku rozwiązaniu zrelaksowanego zadania uzyskujemy optymalną wartość wektora y = \hat{y}^k, i wartość funkcji celu będącą wartością oszacowania górnego \tilde{z}^k.
  • Krok 2. Rozwiąż zadanie restrykcyjne D1(y) podstawiając y = \hat{y}^kW wyniku rozwiązania restrykcji zadania uzyskujemy  optymalną wartość wektora zmiennych dualnych \hat{v}^kNa jego podstawie oraz wartości \hat{y}^k można obliczyć oszacowanie dolne \underline{z}^k w k-tej iteracji.
  •  Krok 3.  Jeżeli \tilde{z}^k- \underline{z}^k < \epsilon to  \hat{y}^k jest rozwiązaniem optymalnym problemu (P), idź do kroku 4 w celu wyznaczeniu optymalnej wartości x. W p.p. podstaw k = k + 1 i idź do kroku 1.
  • Krok 4. Rozwiąż problem PX(y) przyjmując  y = \hat{y}^k. STOP.
Iteracyjny algorytm Bendersa znajduje rozwiązanie w co najwyżej K iteracjach, gdzie K to liczba punktów wierzchołkowych zadania dualnego Bendersa.
Uwaga. Dekompozycja 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.