Generowanie kolumn

Generowanie kolumn lub opóźnione generowanie kolumn jest wydajnym algorytmem rozwiązywania dużych programów liniowych .

Nadrzędną ideą jest to, że wiele programów liniowych jest zbyt dużych, aby jawnie uwzględnić wszystkie zmienne. Chodzi o to, aby zacząć od rozwiązania rozważanego programu tylko z podzbiorem jego zmiennych. do programu dodawane są zmienne, które mogą poprawić funkcję celu . Gdy można wykazać, że dodanie nowych zmiennych nie poprawiłoby już wartości funkcji celu, procedura zostaje zatrzymana. Podczas stosowania algorytmu generowania kolumn istnieje nadzieja, że zostanie wygenerowany tylko bardzo mały ułamek zmiennych. Nadzieję tę potwierdza fakt, że w rozwiązaniu optymalnym większość zmiennych będzie niepodstawowa i przyjmie wartość zero, więc rozwiązanie optymalne można znaleźć bez nich.

W wielu przypadkach ta metoda pozwala rozwiązywać duże programy liniowe, które w innym przypadku byłyby trudne. Klasycznym przykładem problemu, w którym jest on z powodzeniem stosowany, jest problem materiału do cięcia . Jedną szczególną techniką programowania liniowego, która wykorzystuje tego rodzaju podejście, jest dekompozycji Dantziga-Wolfe'a . Ponadto generowanie kolumn zostało zastosowane do wielu problemów, takich jak planowanie załogi , wyznaczanie tras pojazdów i problem pojemnościowej p-mediany.

Algorytm

Algorytm uwzględnia dwa problemy: problem główny i problem podrzędny. Problem główny jest pierwotnym problemem, w którym rozważany jest tylko podzbiór zmiennych. Podproblem to nowy problem stworzony w celu zidentyfikowania poprawiającej się zmiennej ( tj. takiej , która może poprawić funkcję celu problemu głównego).

Algorytm następnie przebiega w następujący sposób:

Zainicjuj problem główny i podproblem
Rozwiąż główny problem
Wyszukaj poprawiającą się zmienną z podproblemem
Jeśli zostanie znaleziona poprawiająca się zmienna: dodaj ją do problemu głównego, a następnie przejdź do kroku 2
Inaczej: Rozwiązanie problemu głównego jest optymalne. Zatrzymywać się.

Znalezienie poprawiającej się zmiennej

Najtrudniejszą częścią tej procedury jest znalezienie zmiennej, która może poprawić funkcję celu głównego problemu. Można to zrobić, znajdując zmienną o najbardziej ujemnym koszcie zredukowanym (zakładając bez utraty ogólności , że problem jest problemem minimalizacji). Jeśli żadna zmienna nie ma ujemnego kosztu zredukowanego, to aktualne rozwiązanie problemu głównego jest optymalne.

Kiedy liczba zmiennych jest bardzo duża, nie jest możliwe znalezienie poprawiającej się zmiennej poprzez obliczenie wszystkich kosztów zredukowanych i wybranie zmiennej o ujemnym koszcie zredukowanym. Zatem pomysł polega na obliczeniu tylko zmiennej o minimalnym obniżonym koszcie. Można to zrobić za pomocą problemu optymalizacyjnego zwanego podproblemem cenowym, który silnie zależy od struktury pierwotnego problemu. Funkcją celu podproblemu jest zredukowany koszt poszukiwanej zmiennej w stosunku do bieżących zmiennych dualnych, a ograniczenia wymagają, aby zmienna była zgodna z naturalnie występującymi ograniczeniami. Metoda generowania kolumn jest szczególnie wydajna, gdy ta struktura umożliwia rozwiązanie podproblemu za pomocą wydajnego algorytmu, zazwyczaj dedykowanego algorytmu kombinatorycznego .

Wyjaśnimy teraz szczegółowo, jak i dlaczego obliczać obniżony koszt zmiennych. Rozważ następujący program liniowy w postaci standardowej:

{\ Displaystyle {\ rozpocząć {wyrównane} & \ min _ {x} c ^ {T} x \\& {\ tekst {poddane}} \\ &Ax=b\\&x\w \mathbb {R} ^{+}\end{wyrównane}}}

który będziemy nazywać problemem pierwotnym oraz jego dualnym programem liniowym :

{\ Displaystyle {\ rozpocząć {wyrównane} i \ max _ {u} u ^ {T} b \\& {\ tekst {poddane}} \\ &u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}}

$Co$ , niech będą optymalnymi rozwiązaniami tych dwóch problemów, które może zapewnić dowolny $solver$ Rozwiązania te weryfikują ograniczenia ich programu liniowego i dzięki dwoistości mają tę samą wartość funkcji celu ( ${\ Displaystyle c ^ {T} x ^ {*} = u ^ {* T } b}$ ), które będziemy nazywać ${\ Displaystyle z ^ {*}}$ . Ta optymalna wartość jest funkcją różnych współczynników pierwotnego problemu: ${\ Displaystyle z ^ {*} = z ^ {*} (c, A, b)}$ . Zauważ $,$ że istnieje podwójna zmienna pierwotnego modelu liniowego Można pokazać, że optymalną zmienną dualną można interpretować jako $}$ cząstkową wartości optymalnej celu $\ Displaystyle u_ {i} ^ {*$ funkcja w odniesieniu do współczynnika $po$ prawej stronie ograniczeń: $frac {\ częściowe z ^ {*}} {\ częściowe b_ {i}}}}$ $u_ {i} ^ {*} = {$ ou bis ${\ Displaystyle u ^ {*} = {\ Frac {\ częściowe z ^ {*} }{\częściowe b}}}$ . $wzrasta$ prościej, wskazuje $,$ o ile lokalnie wzrasta optymalna wartość funkcji celu, gdy jedną

$Rozważmy teraz$ że zmienna nie była dotąd brana pod uwagę w pierwotnym problemie. Zauważ, że jest to $równoznaczne$ ze stwierdzeniem, że zmienna obecna w modelu, ale przyjęła wartość zerową. Zaobserwujemy teraz wpływ na pierwotny problem zmiany wartości ${y}}}$ { \ $\$ $hat$ . Jeśli $}$ odpowiednio $c_ {y}$ związanymi ze zmienną w funkcji celu i ograniczeniach, to program liniowy jest modyfikowany do $displaystyle$ następująco:

{\ Displaystyle {\ rozpocząć {wyrównane} i \ min _ {x} c ^ {T} x + c_ { y}{\kapelusz {y}}\\&{\text{podlega}}\\&Ax=b-A_{y}{\kapelusz {y}}\\&x\w \mathbb {R} ^{+ }\end{wyrównane}}}

Aby wiedzieć, czy dodanie zmiennej do problemu (tj. przyjęcie wartości niezerowej) jest interesujące $z$ chcemy wiedzieć , czy wartość $y}} ^ {*}}$ $\ displaystyle z_ { \ hat$ $y$ funkcji celu tego nowego problemu maleje wraz ze wzrostem wartości zmiennej $}}}$ . Innymi słowy, chcemy wiedzieć ${\ Displaystyle {\ Frac {dz _ {\ kapelusz {y}} ^ {*}} {d {\ kapelusz {y}}}}}$ . Aby to zrobić, zauważ, że $można$ ${\ Displaystyle z _ {\ kapelusz {y}} ^ {*} = c_ {y} {\ kapelusz {y}} + z ^ {*} (c,A,b-A_{y}{\kapelusz {y}})}$ zgodnie z wartością funkcji celu początkowego . Możemy wtedy obliczyć interesującą nas pochodną:

{\ Displaystyle {\ rozpocząć { wyrównane}{\frac {dz_{\kapelusz {y}}^{*}}{d{\kapelusz {y}}}}&~=~&&{\frac {\częściowe z_{\kapelusz {y}}^ {*}}{\częściowy {\kapelusz {y}}}}+{\frac {dz^{*}}{d{\kapelusz {y}}}}\\&~=~&&c_{y}+{ \frac {\częściowe z^{*}}{\częściowe c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\częściowe z^{*}}{\częściowe A}}{\frac {dA}{d{\kapelusz {y}}}}+{\frac {\częściowe z^{*}}{\częściowe b}}{\frac {db}{d{\kapelusz {y}}}}\\&~=~&&c_{y}+{\frac {\częściowe z^{*}}{\częściowe b}}{\frac {db}{d{\kapelusz {y}} }}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{wyrównane} }}

$y}}}$ słowy, wpływ zmiany wartości na wartość na dwa terminy ${\ Displaystyle { \ hat$ . Po pierwsze, zmiana ta bezpośrednio wpływa na funkcję celu, a po drugie, prawa strona ograniczeń jest modyfikowana, co ma wpływ na optymalne zmienne, których wielkość jest mierzona za pomocą zmiennych dualnych u. ${\ displaystyle u ^ {*}}$ $\ Displaystyle x ^ {*}}$ . re ${\ Displaystyle {\ Frac {dz _ {\ kapelusz {y}} ^ {*}} {d {\ kapelusz {y}}}}} jest$ nazywany obniżonym kosztem zmienna $i$ będzie oznaczana dalej przez $y}} .$