Relaksacja programowania liniowego

(Ogólny) program całkowitoliczbowy i jego LP-relaksacja

W matematyce relaksacja (mieszanego) programu liniowego liczb całkowitych jest problemem, który powstaje w wyniku usunięcia ograniczenia integralności każdej zmiennej.

Na przykład w programie całkowitoliczbowym 0–1 wszystkie ograniczenia mają postać

{\ Displaystyle x_ {i} \ w \ {0,1 \}}

.

Zamiast tego relaksacja oryginalnego programu całkowitoliczbowego wykorzystuje zbiór ograniczeń liniowych

{\ Displaystyle 0 \ równoważnik x_ {i} \ równoważnik 1.}

Wynikowa relaksacja jest programem liniowym , stąd nazwa. Ta technika relaksacji przekształca NP-trudny problem optymalizacji (programowanie całkowitoliczbowe) w powiązany problem, który można rozwiązać w czasie wielomianowym (programowanie liniowe); rozwiązanie swobodnego programu liniowego można wykorzystać do uzyskania informacji o rozwiązaniu oryginalnego programu całkowitoliczbowego.

Przykład

₀ Rozważmy problem zbioru pokrycia , którego relaksację programowania liniowego po raz pierwszy rozważał Lovász (1975) . W tym zadaniu jako dane wejściowe podaje się rodzinę zbiorów F = { S , S ₁ , ...}; zadaniem jest znalezienie podrodziny, z jak najmniejszą liczbą zbiorów, mającą ten sam związek co F .

Aby sformułować to jako program całkowitoliczbowy 0–1, utwórz Si _zmienną wskaźnikową x _i dla każdego zbioru S _i , który przyjmuje wartość 1, gdy należy do wybranej podrodziny, a 0, gdy nie należy. Wtedy poprawne pokrycie można opisać przez przypisanie wartości zmiennym wskaźnikowym spełniającym ograniczenia

{\ Displaystyle \ textstyle x_ {i} \ w \ {0,1 \}}

(to znaczy dozwolone są tylko określone wartości zmiennych wskaźnikowych) i dla każdego elementu e _j sumy F ,

{\ Displaystyle \ textstyle \ suma _ {\ {i \ mid e_ {j} \ w S_ {i} \}} x_ {i} \ geq 1}

(czyli każdy element jest objęty). Minimalne pokrycie zestawu odpowiada przypisaniu zmiennych wskaźnikowych spełniających te ograniczenia i minimalizujących liniową funkcję celu

{\ Displaystyle \ textstyle \ min \ suma _ {i} x_ {i}.}

Relaksacja programowania liniowego problemu pokrycia zestawu opisuje pokrycie ułamkowe , w którym zestawom wejściowym przypisuje się wagi takie, że całkowita waga zestawów zawierających każdy element wynosi co najmniej jeden, a całkowita waga wszystkich zestawów jest zminimalizowana.

Jako konkretny przykład problemu zestawu okładek rozważ instancję F = {{ a , b }, { b , c }, { a , c }}. Istnieją trzy optymalne okładki zestawów, z których każdy zawiera dwa z trzech podanych zestawów. Zatem optymalna wartość funkcji celu odpowiedniego programu liczb całkowitych 0–1 wynosi 2, czyli liczba zestawów w optymalnych pokryciach. Istnieje jednak rozwiązanie ułamkowe, w którym każdemu zbiorowi przypisuje się wagę 1/2, a całkowita wartość funkcji celu wynosi 3/2. Zatem w tym przykładzie relaksacja programowania liniowego ma wartość inną niż wartość nierelaksowanego programu całkowitoliczbowego 0–1.

Jakość rozwiązań zrelaksowanych i oryginalnych programów

Relaksację programowania liniowego programu całkowitoliczbowego można rozwiązać za pomocą dowolnej standardowej techniki programowania liniowego. Jeśli okaże się, że optymalne rozwiązanie programu liniowego ma wszystkie zmienne 0 lub 1, będzie to również optymalne rozwiązanie pierwotnego programu całkowitoliczbowego. Jednak generalnie nie jest to prawdą, z wyjątkiem niektórych szczególnych przypadków (np. problemów z całkowicie jednomodułowymi specyfikacjami macierzy).

Jednak we wszystkich przypadkach jakość rozwiązania programu liniowego jest co najmniej tak dobra, jak programu całkowitoliczbowego, ponieważ każde rozwiązanie programu całkowitoliczbowego byłoby również poprawnym rozwiązaniem programu liniowego. Oznacza to, że w problemie maksymalizacji program zrelaksowany ma wartość większą lub równą wartości programu oryginalnego, podczas gdy w problemie minimalizacji, takim jak problem z zestawem okładek, program zrelaksowany ma wartość mniejszą lub równą wartości programu oryginalny program. Zatem relaksacja zapewnia optymistyczne ograniczenie rozwiązania programu całkowitoliczbowego.

W przykładowym przypadku opisanego powyżej problemu z zestawem pokrycia, w którym relaksacja ma optymalną wartość rozwiązania 3/2, możemy wywnioskować, że optymalna wartość rozwiązania nierelaksowanego programu całkowitoliczbowego jest co najmniej tak samo duża. Ponieważ problem pokrycia zestawu ma wartości rozwiązania, które są liczbami całkowitymi (liczba zbiorów wybranych w podrodzinie), optymalna jakość rozwiązania musi być co najmniej tak duża jak kolejna większa liczba całkowita, 2. Zatem w tym przypadku, pomimo posiadania innego wartości z nierozluźnionego problemu, relaksacja programowania liniowego daje nam wąską dolną granicę jakości rozwiązania pierwotnego problemu.

Luka aproksymacji i integralności

Relaksacja programowania liniowego jest standardową techniką projektowania algorytmów aproksymacyjnych dla trudnych problemów optymalizacyjnych. W tej aplikacji ważnym pojęciem jest luka całkowa , czyli maksymalny stosunek jakości rozwiązania programu całkowitoliczbowego do jego relaksacji. W przypadku problemu minimalizacji, jeśli minimum rzeczywiste (minimum problemu liczb całkowitych) to , a minimum relaksacyjne (minimum relaksacji programowania liniowego) to ${\ displaystyle M _ {\ text {int}}}$ ${\ Displaystyle M _ {\ tekst {frac}}}$ $_$ luka wystąpienia W problemie maksymalizacji ułamek jest odwrócony. Luka integralności wynosi zawsze co najmniej 1. W powyższym przykładzie instancja F = {{ a , b }, { b , c }, { a , c }} pokazuje lukę integralności równą 4/3.

Zazwyczaj luka integralności przekłada się na współczynnik aproksymacji algorytmu aproksymacji. Dzieje się tak, ponieważ algorytm aproksymacji opiera się na pewnej strategii zaokrąglania, która znajduje dla każdego zrelaksowanego rozwiązania o rozmiarze $,$ rozwiązanie o rozmiarze co najwyżej $\ displaystyle RR\cdot M_{\text{frac}}}$ (gdzie RR to współczynnik zaokrąglenia). Jeśli istnieje instancja z luką integralności IG , to każdy strategia zaokrąglania zwróci w tym przypadku zaokrąglone rozwiązanie o rozmiarze co najmniej ${\ Displaystyle M _ {\ text {int}} = IG \ cdot M _ {\ text {frac}}}$ . Dlatego koniecznie ${\ Displaystyle RR \ geq IG}$ . Współczynnik zaokrąglenia RR jest tylko górną granicą współczynnika aproksymacji, więc teoretycznie rzeczywisty współczynnik aproksymacji może być niższy niż IG , ale może to być trudne do udowodnienia. W praktyce duży IG zwykle oznacza, że współczynnik aproksymacji w relaksacji programowania liniowego może być zły i może lepiej poszukać innych schematów aproksymacji dla tego problemu.

W przypadku problemu okładki Lovász udowodnił, że luka całkowa dla przypadku z n elementami to H _n , n- ta liczba harmoniczna . Relaksację programowania liniowego dla tego problemu można przekształcić w przybliżone rozwiązanie oryginalnej nierelaksowanej instancji okładki zestawu za pomocą techniki zaokrąglania losowego ( Raghavan & Tompson 1987 ) . Biorąc pod uwagę pokrycie ułamkowe, w którym każdy zestaw S _i ma wagę w _i , wybierz losowo wartość każdej zmiennej wskaźnikowej x _{i 0–1} , aby wynosiła 1 z prawdopodobieństwem w _i × (ln n +1), aw przeciwnym razie 0. Wtedy każdy element e _j ma prawdopodobieństwo mniejsze niż 1/( e × n ) pozostania odkrytym, więc ze stałym prawdopodobieństwem wszystkie elementy są zakryte. Pokrywa wygenerowana tą techniką ma całkowity rozmiar, z dużym prawdopodobieństwem, (1+o(1))(ln n ) W , gdzie W jest całkowitą masą roztworu ułamkowego. Zatem ta technika prowadzi do losowego algorytmu aproksymacji, który znajduje ustalone pokrycie w logarytmicznym współczynniku optimum. Jak Young (1995) , zarówno część losowa tego algorytmu, jak i konieczność konstruowania jawnego rozwiązania relaksacji programowania liniowego można wyeliminować metodą prawdopodobieństw warunkowych , prowadząc do deterministycznego algorytmu zachłannego dla okładki zestawu, znanej już Lovászowi, polegającej na wielokrotnym wybieraniu zestawu, który obejmuje jak największą liczbę pozostałych nieosłoniętych elementów. Hn _Ten zachłanny algorytm przybliża pokrycie zestawu do tego samego czynnika , który Lovász udowodnił jako lukę integralności dla zestawu. Istnieją silne przesłanki oparte na teorii złożoności, aby sądzić, że żaden algorytm aproksymacji czasu wielomianowego nie może osiągnąć znacznie lepszego współczynnika aproksymacji ( Feige 1998 ).

Podobne techniki zaokrąglania losowego i derandomizowane algorytmy aproksymacji mogą być używane w połączeniu z relaksacją programowania liniowego w celu opracowania algorytmów aproksymacji dla wielu innych problemów, jak opisali Raghavan, Tompson i Young.

Branch i związany z dokładnymi rozwiązaniami

Oprócz zastosowań w aproksymacji, programowanie liniowe odgrywa ważną rolę w algorytmach rozgałęzionych i ograniczonych do obliczania prawdziwie optymalnego rozwiązania trudnych problemów optymalizacyjnych.

Jeśli niektóre zmienne w rozwiązaniu optymalnym mają wartości ułamkowe, możemy rozpocząć proces typu rozgałęzionego i związanego , w którym rekurencyjnie rozwiązujemy podproblemy, w których niektóre zmienne ułamkowe mają swoje wartości ustalone na zero lub jeden. W każdym kroku algorytmu tego typu rozważamy podproblem pierwotnego programu całkowitoliczbowego 0–1, w którym niektórym zmiennym przypisano wartości 0 lub 1, a pozostałym zmiennym nadal wolno przyjąć albo wartość. W podproblemie i niech V _i oznaczają zbiór pozostałych zmiennych. Proces rozpoczyna się od rozważenia podproblemu, w którym nie zostały przypisane żadne wartości zmiennych i w którym V ₀ jest całym zbiorem zmiennych pierwotnego problemu. Następnie dla każdego podproblemu i wykonuje następujące kroki.

Oblicz optymalne rozwiązanie relaksacji programowania liniowego bieżącego podproblemu. Oznacza to, że dla każdej zmiennej x _j w VI _, zastępujemy ograniczenie, że x _{j wynosi 0 lub 1} ograniczeniem rozluźnionym, aby mieściło się w przedziale [0,1]; jednak zmienne, którym już przypisano wartości, nie są rozluźniane.
Jeśli zrelaksowane rozwiązanie bieżącego podproblemu jest gorsze niż najlepsze znalezione do tej pory rozwiązanie całkowitoliczbowe, wycofaj się z tej gałęzi wyszukiwania rekurencyjnego.
Jeśli zrelaksowane rozwiązanie ma wszystkie zmienne ustawione na 0 lub 1, przetestuj je z najlepszym znalezionym dotychczas rozwiązaniem całkowitym i zachowaj to, które z dwóch rozwiązań jest najlepsze.
W przeciwnym razie niech x _j będzie dowolną zmienną, która ma wartość ułamkową w zrelaksowanym rozwiązaniu. Utwórz dwa podproblemy, jeden, w którym x _j jest ustawiony na 0, a drugi, w którym x _j jest ustawiony na 1; w obu podproblemach nadal stosowane są dotychczasowe przypisania wartości do niektórych zmiennych, więc zbiór pozostałych zmiennych przyjmuje postać V _i \ { x _j }. Przeszukaj rekurencyjnie oba podproblemy.

Chociaż trudno jest udowodnić teoretyczne granice działania algorytmów tego typu, w praktyce mogą one być bardzo skuteczne.

Metoda płaszczyzny cięcia

Dwa programy całkowitoliczbowe 0–1, które są równoważne, ponieważ mają tę samą funkcję celu i ten sam zestaw możliwych rozwiązań, mogą mieć zupełnie różne relaksacje programowania liniowego: relaksacja programowania liniowego może być postrzegana geometrycznie, jako wypukła polytope, która obejmuje wszystkie wykonalne rozwiązania i wyklucza wszystkie inne wektory 0–1, a nieskończenie wiele różnych polytopów ma tę właściwość. Idealnie byłoby użyć wypukłej otoczki jako relaksacji możliwych rozwiązań; programowanie liniowe na tym polytopie automatycznie dałoby poprawne rozwiązanie oryginalnego programu całkowitoliczbowego. Jednak ogólnie rzecz biorąc, ten polytope będzie miał wykładniczo wiele aspektów i będzie trudny do skonstruowania. Typowe relaksacje, takie jak relaksacja omówionego wcześniej problemu pokrycia zestawu, tworzą polytope, który ściśle zawiera wypukły kadłub i ma wierzchołki inne niż wektory 0–1, które rozwiązują problem nierozluźniony.

Metoda płaszczyzny tnącej do rozwiązywania programów całkowitych 0–1, po raz pierwszy wprowadzona dla problemu komiwojażera przez Dantziga, Fulkersona i Johnsona (1954) i uogólniona na inne programy całkowitoliczbowe przez Gomory'ego (1958) , wykorzystuje tę wielość możliwych relaksacji, znajdując sekwencję relaksacji, które ściślej ograniczają przestrzeń rozwiązań, aż w końcu uzyskuje się rozwiązanie całkowite. Ta metoda rozpoczyna się od dowolnej relaksacji danego programu i znajduje optymalne rozwiązanie za pomocą solwera programowania liniowego. Jeśli rozwiązanie przypisuje wartości całkowite wszystkim zmiennym, jest to również optymalne rozwiązanie problemu nierozluźnionego. W przeciwnym razie dodatkowe wiązanie liniowe ( płaszczyzna cięcia lub cięcie ) oddziela wynikowe rozwiązanie ułamkowe od wypukłej otoczki rozwiązań całkowitych, a metoda powtarza się dla tego nowego, bardziej ograniczonego problemu.

Potrzebne są metody specyficzne dla problemu, aby znaleźć cięcia stosowane w tej metodzie. Szczególnie pożądane jest znalezienie płaszczyzn tnących, które tworzą ścianki wypukłej powłoki rozwiązań całkowitych, ponieważ te płaszczyzny są tymi, które najbardziej ograniczają przestrzeń rozwiązania; zawsze istnieje płaszczyzna tnąca tego typu, która oddziela dowolne rozwiązanie ułamkowe od rozwiązań całkowitych. Przeprowadzono wiele badań nad metodami znajdowania tych aspektów dla różnych typów kombinatorycznych problemów optymalizacyjnych w ramach kombinatoryki wielościennej ( Aardal & Weismantel 1997 ).

Powiązana metoda rozgałęzienia i cięcia łączy metodę płaszczyzny cięcia oraz metody rozgałęzienia i ograniczenia. W każdym podproblemie uruchamia metodę płaszczyzny tnącej, dopóki nie można znaleźć więcej płaszczyzn tnących, a następnie rozgałęzia się na jednej z pozostałych zmiennych ułamkowych.

Zobacz też

Kolorowanie ułamkowe , relaksacja programowania liniowego kolorowania grafów .
Zaokrąglanie losowe , w celu uzyskania rozwiązania pierwotnego problemu z rozwiązania relaksacji.

Aardal, Karen ; Weismantel, Robert (1997), „Kombinatoryka wielościenna: bibliografia z adnotacjami” , Bibliografie z adnotacjami w optymalizacji kombinatorycznej (PDF) , Wiley .
Agmon, Shmuel (1954), „Metoda relaksacji nierówności liniowych” , Canadian Journal of Mathematics , 6 : 382–392, doi : 10.4153/CJM-1954-037-2 .
Gdańsk, Jerzy ; Fulkerson, DR ; Johnson, Selmer (1954), „Rozwiązanie problemu komiwojażera na dużą skalę”, Journal of the Operations Research Society of America , 2 (4): 393–410, doi : 10.1287 / opre.2.4.393 .
Feige, Uriel (1998), „Próg ln n dla przybliżonej okładki zestawu”, Journal of the ACM , 45 (4): 634–652, CiteSeerX 10.1.1.70.5014 , doi : 10.1145/285055.285059 .
Gomory, Ralph E. (1958), „Zarys algorytmu rozwiązań całkowitoliczbowych programów liniowych”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , 64 (5): 275–279, doi : 10.1090 / S0002-9904-1958-10224- 4 .
Lovász, László (1975), „O stosunku optymalnych pokrycia całkowego i ułamkowego”, Discrete Mathematics , 13 (4): 383–390, doi : 10.1016/0012-365X (75) 90058-8 .
Motzkin, TS ; Schoenberg, IJ (1954), „Metoda relaksacji nierówności liniowych” , Canadian Journal of Mathematics , 6 : 393–404, doi : 10,4153/CJM-1954-038-x .
Raghavan, Prabhakar; Thompson, Clark D. (1987), „Randomizowane zaokrąglanie: technika zapewniania dobrych algorytmów i dowodów algorytmicznych”, Combinatorica , 7 (4): 365–374, doi : 10.1007 / BF02579324 .
Young, Neal E. (1995), „Zaokrąglanie losowe bez rozwiązywania programu liniowego”, Proc. 6 Symp. ACM-SIAM Dyskretne algorytmy (SODA) , Soda '95, s. 170–178, ISBN 9780898713497 .