Generowanie kolumn - Column generation

Generowanie kolumn lub opóźnione generowanie kolumn to wydajny algorytm rozwiązywania dużych programów liniowych .

Ogólną ideą jest to, że wiele programów liniowych jest zbyt dużych, aby jawnie uwzględnić wszystkie zmienne. Założeniem jest, że większość zmiennych będzie niepodstawowa i w optymalnym rozwiązaniu przyjmie wartość zero. Z tego powodu przy rozwiązywaniu problemu teoretycznie należy wziąć pod uwagę tylko podzbiór zmiennych. Generowanie kolumn wykorzystuje ten pomysł do generowania tylko tych zmiennych, które mają potencjał do poprawy funkcji celu - to znaczy do znalezienia zmiennych o ujemnym obniżonym koszcie (przy założeniu bez utraty ogólności, że problem jest problemem minimalizacji).

Rozwiązany problem jest podzielony na dwa problemy: problem główny i podproblem. Główny problem jest pierwotnym problemem, uwzględniającym tylko podzbiór zmiennych. Podproblem jest nowym problemem utworzonym w celu zidentyfikowania nowej zmiennej. Celem funkcji podproblemu jest zmniejszony koszt nowej zmiennej w stosunku do obecnych zmiennych dualnych, a ograniczenia wymagają, aby zmienna spełniała ograniczenia występujące naturalnie.

Proces przebiega następująco. Główny problem został rozwiązany - z tego rozwiązania jesteśmy w stanie uzyskać ceny dualne dla każdego z ograniczeń w zadaniu głównym. Informacje te są następnie wykorzystywane w funkcji celu podproblemu. Podproblem został rozwiązany. Jeżeli obiektywna wartość podproblemu jest ujemna, zidentyfikowano zmienną o ujemnym koszcie obniżonym. Ta zmienna jest następnie dodawana do głównego problemu, a główny problem jest ponownie rozwiązywany. Ponowne rozwiązanie problemu głównego wygeneruje nowy zestaw podwójnych wartości, a proces będzie powtarzany, dopóki nie zostaną zidentyfikowane żadne negatywne zmienne o zmniejszonych kosztach. Podproblem zwraca rozwiązanie o nieujemnych obniżonych kosztach, możemy stwierdzić, że rozwiązanie problemu głównego jest optymalne.

W wielu przypadkach pozwala to na rozwiązanie dużych programów liniowych, które wcześniej uważano za trudne do wykonania. Klasycznym przykładem problemu, w którym jest to z powodzeniem stosowane, jest problem z cięciem . Jedną z technik programowania liniowego, w której stosuje się tego rodzaju podejście, jest algorytm rozkładu Dantziga – Wolfe'a . Ponadto generowanie kolumn zostało zastosowane do wielu problemów, takich jak planowanie załogi , wyznaczanie tras pojazdów i problem z pojemnością p-mediany .