Konfiguracja programu liniowego

Konfiguracyjny program liniowy ( configuration-LP ) jest szczególnym programem liniowym używanym do rozwiązywania kombinatorycznych problemów optymalizacyjnych. Została ona wprowadzona w kontekście problemu rozbioru . Później zastosowano go do pakowania w pojemniki i planowania zadań . W konfiguracji-LP istnieje zmienna dla każdej możliwej konfiguracji - każdego możliwego multisetu elementów, które mieszczą się w jednym pojemniku (konfiguracje te są również znane jako wzorce ). Zwykle liczba konfiguracji jest wykładnicza w stosunku do rozmiaru problemu, ale w niektórych przypadkach możliwe jest osiągnięcie przybliżonych rozwiązań przy użyciu tylko wielomianowej liczby konfiguracji.

W opakowaniu do kosza

Integralny LP

W problemie pakowania do pojemników istnieje n przedmiotów o różnych rozmiarach. Celem jest spakowanie przedmiotów do minimalnej liczby pojemników, z których każdy może zawierać maksymalnie B . Możliwa konfiguracja to zbiór rozmiarów o sumie co najwyżej B .

• Przykład : załóżmy, że rozmiary przedmiotów to 3,3,3,3,3,4,4,4,4,4, a B = 12. Wtedy możliwe konfiguracje to: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Gdybyśmy mieli tylko trzy przedmioty o rozmiarze 3, nie moglibyśmy użyć konfiguracji 3333.

Oznaczmy przez S zestaw różnych rozmiarów (i ich liczbę). Oznaczmy przez C zbiór różnych konfiguracji (i ich liczbę). Dla każdego rozmiaru s w S i konfiguracji c w C oznacz:

• n _s - liczba elementów o rozmiarze s .
• a _{s , c} - liczba wystąpień wielkości s w konfiguracji c .
• x _c - zmienna oznaczająca liczbę pojemników o konfiguracji c .

Wtedy LP konfiguracji bin-packingu to:

${c \ w C} x_ {c} ~ ~ ~ {\ tekst {z zastrzeżeniem}}}$

$_$ _ _ _ _ _ pakowane jest n _s przedmiotów o rozmiarze s ).

${\ Displaystyle x_ {c} \ in \ {0, \ ldots, n \}}$ dla wszystkich c w C (- ogólnie jest co najwyżej n pojemników, więc co najwyżej n każdego indywidualna konfiguracja).

Konfiguracja LP jest całkowitoliczbowym programem liniowym , więc generalnie jest NP-trudna. Co więcej, nawet sam problem jest ogólnie bardzo duży: ma C i ograniczenia S. Jeśli najmniejszym rozmiarem elementu jest eB (dla pewnego ułamka e w (0,1)), to w każdym koszu może znajdować się do 1/ e elementów, więc liczba konfiguracji C ~ S ^{1/ e} , która może być bardzo duża, jeśli e jest małe (jeśli e jest uważane za stałą, to liczbę całkowitą LP można rozwiązać przez wyczerpujące przeszukiwanie: istnieje co najwyżej konfiguracja S ^1/e , a dla każdej konfiguracji jest co najwyżej n możliwych wartości, więc jest co najwyżej większość kombinacji do $,$ Dla każdej kombinacji musimy sprawdzić ${ \displaystyle S \ cdot n ^ {S ^ {1/e}}}$ wykonania to , co jest wielomianem w n , gdy S, e są stałe).

Jednak ten ILP służy jako podstawa dla kilku algorytmów aproksymacji. Główną ideą tych algorytmów jest zredukowanie oryginalnej instancji do nowej instancji, w której S jest małe, a e jest duże, więc C jest stosunkowo małe. Następnie ILP można rozwiązać albo przez pełne przeszukanie (jeśli S , C są wystarczająco małe), albo przez rozluźnienie go do ułamkowego LP.

Ułamkowy LP

Ułamkowa konfiguracja LP bin-packingu Jest to relaksacja programowania liniowego powyższego ILP. ${\ Displaystyle x_ {c} \ geq 0 }$ ostatnie ograniczenie ograniczeniem ${\ Displaystyle x_ {c} \ in \ {0, \ ldots, n \}}$ x . Innymi słowy, każdej konfiguracji można użyć ułamkową liczbę razy. Relaksacja została po raz pierwszy przedstawiona przez Gilmore'a i Gomory'ego i jest często nazywana programem liniowym Gilmore'a-Gomory'ego .

• Przykład : załóżmy, że jest 31 elementów o rozmiarze 3 i 7 elementów o rozmiarze 4, a rozmiar pojemnika to 10. Konfiguracje to: 4, 44, 34, 334, 3, 33, 333. Ograniczenia to [0,0 ,1,2,1,2,3]* x =31 i [1,2,1,1,0,0,0]* x =7. Optymalnym rozwiązaniem ułamkowego LP jest [0,0,0,7,0,0,17/3] To znaczy: jest 7 pojemników o konfiguracji 334 i 17/3 pojemników o konfiguracji 333. Zauważ, że tylko dwie różne konfiguracje są potrzebne.

W skrócie ułamkowy LP można zapisać w następujący sposób:

${\ Displaystyle {\ tekst {minimalizuj}} ~ ~ \ mathbf {1} \ cdot \ mathbf {x} ~~~ {\ tekst {st}} ~ ~ A \ mathbf {x} \ geq \mathbf {n} ~~~{\text{i}}~~\mathbf {x} \geq 0}$

Gdzie 1 to wektor (1,...,1) o rozmiarze C , A to macierz S na C , w której każda kolumna reprezentuje pojedynczą konfigurację, a n to wektor ( n ₁ ,..., n _S. ).

Rozwiązywanie ułamkowego LP

Program liniowy bez ograniczeń integralności można rozwiązać w wielomianie czasu w liczbie zmiennych i ograniczeniach. Problem polega na tym, że liczba zmiennych w konfiguracji ułamkowej LP jest równa liczbie możliwych konfiguracji, które mogą być ogromne. Karmarkar i Karp przedstawiają algorytm, który rozwiązuje ten problem.

Najpierw konstruują dualny program liniowy ułamkowego LP:

${\ Displaystyle {\ tekst {maksymalizuj}} ~ ~ \ mathbf {n} \ cdot \ mathbf {y} ~ ~ ~ {\ tekst {st}} ~ ~ A ^ {T} \ mathbf {y} \leq \mathbf {1} ~~~{\text{i}}~~\mathbf {y} \geq 0}$ .

Ma S zmiennych y ₁ , ..., y _S i C ${\ Displaystyle A ^ {c} \ cdot y \ równoważnik 1}$ : dla każdej konfiguracji c , istnieje ograniczenie , gdzie $\ displaystyle A ^ {c}}$ jest kolumną A reprezentującą konfigurację do . 3 Ma następującą interpretację ekonomiczną. Dla każdego rozmiaru s powinniśmy wyznaczyć nieujemną cenę y _s . Nasz zysk to łączna cena wszystkich przedmiotów. Chcemy maksymalizować zysk n y pod warunkiem, że łączna cena przedmiotów w każdej konfiguracji wynosi co najwyżej 1.

Po drugie, stosują wariant metody elipsoidalnej , który nie musi wymieniać wszystkich ograniczeń — wystarczy wyrocznia separacji . Wyrocznia separacji to algorytm, który przy danym wektorze y albo stwierdza, że ​​jest to wykonalne, albo znajduje ograniczenie, które narusza. Wyrocznię separacji dla podwójnego LP można zaimplementować, rozwiązując problem plecakowy z rozmiarami s i wartościami y : jeśli optymalne rozwiązanie problemu plecakowego ma całkowitą wartość co najwyżej 1, to y jest wykonalne; jeśli jest większy niż 1, to y jest niewykonalne , a optymalne rozwiązanie problemu plecakowego identyfikuje konfigurację, dla której ograniczenie jest naruszone.

Po trzecie, pokazują, że przy przybliżonym rozwiązaniu problemu plecakowego można uzyskać przybliżone rozwiązanie podwójnego LP, a na tej podstawie przybliżone rozwiązanie pierwotnego LP; patrz Algorytmy pakowania bin Karmarkara-Karpa .

W sumie, dla dowolnego współczynnika tolerancji h , znajduje podstawowe wykonalne rozwiązanie kosztu co najwyżej LOPT(I) + h , i biegnie w czasie:

${\ Displaystyle O \ lewo (S ^ {8} \ log {S} \log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh }})\prawo)}$ ,

gdzie S to liczba różnych rozmiarów, n to liczba różnych przedmiotów, a rozmiar najmniejszego elementu to eB . W szczególności, jeśli e ≥ 1/ n i h =1, algorytm znajduje rozwiązanie z co najwyżej przedziałami LOPT+1 w czasie: ${\ Displaystyle O \ lewo (S ^ {8} \ log {S} \ log ^ {2} {n} + S ^ {4} n \ log {S} \ log {n} \ prawo)}$ . Losowy wariant tego algorytmu działa w oczekiwanym czasie:

${\ Displaystyle O \ lewo (S ^ {7} \ log {S} \log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh }})\prawo)}$ .

Zaokrąglanie ułamka LP

Karmarkar i Karp rozwinęli dalej sposób zaokrąglania ułamkowego LP do przybliżonego rozwiązania całkowego LP; patrz Algorytmy pakowania bin Karmarkara-Karpa . Ich dowód pokazuje, że addytywna luka integralności tego LP wynosi O(log ² ( n )). Później Hoberg i Rothvoss poprawili swój wynik i udowodnili, że luka całkowa wynosi O(log( n )). Najbardziej znaną dolną granicą luki integralności jest stała Ω(1). Znalezienie dokładnej luki integralności jest problemem otwartym.

W przykryciu kosza

W zadaniu zakrywania kosza jest n przedmiotów o różnych rozmiarach. Celem jest spakowanie przedmiotów do maksymalnej liczby pojemników, z których każdy powinien zawierać co najmniej B . Naturalną konfiguracją LP dla tego problemu może być:

${\ Displaystyle {\ tekst {maksymalizuj}} ~ ~ \ mathbf {1} \ cdot \ mathbf {x} ~ ~ ~ {\ tekst {st}} ~ ~ A \ mathbf {x} \ lek \mathbf {n} ~~~{\text{i}}~~\mathbf {x} \geq 0}$

gdzie A reprezentuje wszystkie konfiguracje przedmiotów o sumie co najmniej B (można przyjąć tylko konfiguracje z minimalną inkluzją). Problem z tym LP polega na tym, że w przypadku zakrywania pojemników manipulowanie małymi przedmiotami jest problematyczne, ponieważ małe przedmioty mogą być niezbędne do uzyskania optymalnego rozwiązania. Przy dozwolonych małych elementach liczba konfiguracji może być zbyt duża nawet dla techniki Karmarkara i Karpa. Csirik, Johnson i Kenyon przedstawiają alternatywny LP. Najpierw definiują zestaw elementów, które są nazywane small . Niech T będzie całkowitym rozmiarem wszystkich małych przedmiotów. Następnie konstruują macierz A reprezentującą wszystkie konfiguracje o sumie < 2. Następnie rozważają powyższy LP z jednym dodatkowym ograniczeniem:

$${\ Displaystyle {\ tekst {maksymalizuj}} ~ ~ \ mathbf {1} \ cdot \ mathbf {x} ~ ~ {\ tekst {st}}}$$

$${\ Displaystyle A \ mathbf {x} \ równoważnik \ mathbf {n}}$$

$${\ Displaystyle \ suma _ {c \ w C: suma (c) <B} (B- sum(c))\cdot x_{c}\równoważnik T}$$

$${\ Displaystyle \ mathbf {x} \ geq 0}$$

Dodatkowe ograniczenie gwarantuje, że „wolne miejsce” w pojemnikach może zostać wypełnione małymi przedmiotami. Podwójność tego LP jest bardziej złożona i nie można jej rozwiązać za pomocą prostej wyroczni separacji problemu plecakowego. Csirik, Johnson i Kenyon przedstawiają inną metodę rozwiązania tego problemu w przybliżeniu w czasie wykładniczym w 1/epsilon. Jansen i Solis-Oba przedstawiają ulepszoną metodę rozwiązania tego problemu w przybliżeniu w czasie wykładniczym w 1/epsilon.

W harmonogramowaniu maszyn

W problemie planowania niepowiązanych maszyn istnieje kilka m różnych maszyn, które powinny przetwarzać kilka n różnych zadań. Kiedy maszyna i przetwarza zadanie j , zajmuje to czas pi _{, j .} Celem jest podzielenie zadań między maszyny w taki sposób, aby maksymalny czas wykonania maszyny był jak najmniejszy. Wersja decyzyjna tego problemu jest następująca: czy w danym czasie T istnieje partycja, w której czas zakończenia wszystkich maszyn wynosi co najwyżej T ?

Dla każdej maszyny i istnieje skończenie wiele podzbiorów zadań, które maszyna i może wykonać w czasie co najwyżej T. Każdy taki podzbiór nazywany jest konfiguracją dla maszyny i . Oznaczmy przez C _i ( T ) zbiór wszystkich konfiguracji dla maszyny i w danym czasie T . Dla każdej maszyny i $jest$ konfiguracji c w do _ja ( T ) zdefiniuj zmienną równa 1, jeśli rzeczywista konfiguracja używana w maszynie i to , a 0 w przeciwnym razie Zatem ograniczenia LP są następujące:

• ${\ Displaystyle \ suma _ {c \ w C_ {i} (T)} x_ {i, c} = 1}$ dla każdej maszyny ja w 1, .. ., m;
• ${\ Displaystyle \ suma _ {i = 1} ^ {m} \ suma _ {c \ ni j, c \ in C_{i}(T)}x_{i,c}=1}$ dla każdego zadania j w 1,..., n;
• ${\ Displaystyle x_ {i, j} \ w \ {0,1 \}}$ dla każdego ja , jot .

Nieruchomości

Luka integralności konfiguracji-LP dla planowania niepowiązanych maszyn wynosi 2.

Zobacz też

• Pakowanie dużej liczby pojemników