Podręcznik: Relaksacja Lagrange'a

3. Techniki restrykcyjne i relaksacyjne

3.1. Relaksacja Lagrange'a

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.

Funkcja Lagrange'a jest relaksacją zadania optymalizacji, która usuwa ograniczenia z pierwotnego zadania i wprowadza je do funkcji celu, po przemnożeniu przez zmienne

$\lambda$ nazywane mnożnikami Lagrange'a. Funkcję tę, dla zadań MILP zapisujemy jako:

$L(x,\lambda)=\min \; c^T x + \lambda\cdot(g(x)-b),\;\;$ p.o.:

$f(x)\geq d$

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

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.

Problem lokalizacji i dystrybucji towarów. Przypominjmy przykład podobny do omawianego w rozdziale poświęconym implentacji problemów w środowisku IBM Cplex. Zakładamy, że chcemy rozdystrybuować towar pomiędzy

$N$ miastami jak najniższym kosztem, znając zapotrzebowania tych miast. W tym celu musimy zaplanować umiejscowienie magazynów, z których będziemy pobierać towar. W zależności od lokalizacji magazynów będziemy dysponować różnymi pojemnościami.
Oznaczenia, parametry:
cities - zbiór miast oznaczanych indeksami

$i,j$

$c_{ij}$ - koszt zaopatrzenia klientów w mieście

$j$ z magazynu w mieście

$i$

$M_i$ - pojemność magazynu w mieście

$i$

$d_i$ - zapotrzebowanie miasta

$i$

$f_i$ - koszt budowy magazynu w mieście

$i$
Zmienne:

$y_i$ - czy w danym mieście

$i$ wybudować magazyn (zm. binarna)

$x_{ij}$ - procent zapotrzebowania w mieście

$j$ pokrywanego towarem z miasta

$i$ , zmienna ciągła z zakresu

$0\leq x_{ij}\leq 1$
Model matematyczny zadania:

$\min \sum_{ij} d_jc_{ij}x_{ij} +\sum_i f_iy_i$
p.o.:
(1)

$\sum_j d_jx_{ij} \leq M_iy_i\;\;\;\forall i\in \mathrm{cities}$
(2)

$\sum_i x_{ij}= 1\;\;\;\forall j\in \mathrm{cities}$
(3)

$x_{ij}\leq y_i\;\;\;\forall i,j\in \mathrm{cities}$
(4)

$x_{ij}\geq 0,\;\; y_i\in\{0,1\}\;\;\;\forall i,j\in \mathrm{cities}.$
Jedną z możliwych relaksacji jest usunięcie ograniczeń wymuszających zaopatrzenie każdego miasta, czyli ograniczeń (2). Taki zabieg pozwoli na dekompozycję rozważanego problemu na

$N$ zadań rozpatrywanych niezależnie dla każdego miasta. W tym celu wprowadzamy mnożnik

$\lambda_j$ dla

$j$ -tego ograniczenia (2), pomocniczo definiujemy też

$\bar{c}_{ij}=d_jc_{ij}-\lambda_j$ .
Funkcja Lagrange'a wyznaczająca dolne oszacowanie pierwotnego problemu jest wtedy postaci:

$(5) L(x,\lambda) = \min_x \sum_{ij} \bar{c}_{ij}x_{ij} +\sum_i f_iy_i\\ \mathrm{po.}\\ (6) \sum_j d_jx_{ij} \leq M_iy_i\;\;\;\forall i\in \mathrm{cities}\\ (7) x_{ij}\leq y_i\;\;\;\forall i,j\in \mathrm{cities}\\ (8) x_{ij}\geq 0,\;\; y_i\in\{0,1\}\;\;\;\forall i,j\in \mathrm{cities}.$
Dekompozycja problemu. Aby rozwiązać powyższy problem relaksacji Lagrange'a niezależnie dla każdego z miast

$i$ sformułujemy zdekompowany problem postaci:

$L_i = \min_x \sum_{j} \bar{c}_{j}x_{j} + f_iy_i\\ \mathrm{po.}\\ (9) \sum_j d_jx_{j} \leq M_iy_i\\ (10) x_{j}\leq y_i\;\;\;\forall j\in \mathrm{cities}\\ (11) x_{j}\geq 0,\;\; y_i\in\{0,1\}\;\;\;.$ Zadanie

$L_i$ dla konkretnego miasta bardzo łatwo rozwiązać:

gdy $\bar{c}_{j}>0$ wtedy należy przyjąć $x_j=0$ , co oznacza, że $j$ -te miasto nie będzie zaopatrywane z lokalizacji $i$ ;
w p.p. sprawdzamy warunek, czy warto otworzyć magazyn w lokalizacji $i$ w następujący sposób:
- szeregujemy pozostałe zmienne $x_j$ w takiej kolejności, aby $\frac{\bar{c}_1}{d_1}\leq \frac{\bar{c}_2}{d_2}\leq \frac{\bar{c}_3}{d_3}\leq \dots$ ;
- następnie przez przez $k$ oznaczamy najwyższy indeks, dla którego suma kolejnych zapotrzebowań nie przekracza pojemności magazynu $i$ , tj., dla którego jest spełnione ograniczenie $\sum_{j=1}^k d_j\leq M_i$ ; ewentualny zapas pojemności magazynu dzielimy przez zapotrzebowanie miasta następnego w kolejności, czyli wyznaczamy parametr $r$ jako ułamek: $r= \frac{M_i - \sum_{j=1}^k d_j}{d_{k+1}}$ ;
- podejmujemy decyzję o otwarciu magazynu w mieście $i$ , czyli przyjmujemy $y_i=1$ jeśli koszt $f_i+\sum_{j=1}^k\bar{c}_j+r\cdot\bar{c}_{k+1} < 0$ , w p.p. $y_i=0$ ;
- jeśli $y_i=1$ to $x_j=1$ , dla $j=1,\ldots,k$ , natomiast $x_{k+1}=r$ .

Powyższy sposób rozwiązywania indywidualnych problemów jest prosty i efektywny. Ostatnim krokiem jest sprawdzenie jak wiele magazynów otworzyliśmy, gdyż cechą algorytmu jest przypisywanie zbyt małej liczby magazynów. Można takie rozwiązanie dość łatwo poprawić otwierając kolejne najtańsze (o najniższym koszcie otwarcia) magazyny - minimalną liczbę otwartych magazynów

$p$ łatwo wyznaczyć odnosząc się do sumarycznego zapotrzebowania we wszystkich miastach (sumaryczna pojemność

$p$ największych magazynów musi pokrywać całkowite zapotrzebowanie). Analizowana metoda pozwala wyznaczyć dolne oszacowanie optymalnego rozwiązania, należy w tym podejściu tak dobierać wektor mnożników

$\lambda$ , aby uzyskane oszacowanie miało jak najwyższą wartość.
Szczegółowe omówienie przedstawionego tu problemu lokalizacyjnego można znaleźć w pracy Alenezy, Eiman J. "Solving capacitated facility location problem using Lagrangian decomposition and volume algorithm." Advances in Operations Research 2020. Ostatecznie autorzy stosują subgradientową technikę do iteracyjnego wyznaczania mnożników Lagrange'a, w dalszej części tego rozdziału przedstawiamy teoretyczne podstawy tego podejścia.

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:

Wtedy problem pierwotny możemy zdefiniować w postaci:

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

Zadanie dualne zapiszemy wtedy jako:

gdzie ℳ jest zbiorem definiowanym w zależności od relaksowanych m ograniczeń:

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.

Właściwości funkcji dualnej 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.

W praktyce, problem wyznaczania mnożników Lagrange'a, czyli rozwiązanie zadania maksymalizacji wklęsłej, kawałkami liniowej funkcji dualnej

jest realizowane metodami optymalizacji bez ograniczeń, w szczególności tzw. metodą subgradientową. Mnożniki Lagrange'a wyznacza się iteracyjnie, zgodnie ze schematem:

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

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.

Można prześledzić działanie algorytmu iteracyjnego aktualizowania mnożnikó Lagrange'a opierając się na implementacji metody w IBM Cplex. W tym celu należy otworzyć projekt LagrangianRelaxation dostępny w bibliotece przykładów.

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

Nie ma ogólnego schematu wyznaczania rozwiązania dopuszczalnego. Opracowuje się algorytmy przybliżone, startujące z rozwiązania niedopuszczalnego. W zależności od wariantu nie spełnienia rozwiązania dopuszczalnego możliwe są różne reguły poprawy doprowadzające aktualne rozwiązanie do dopuszczalnego.

Obszary badań

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