Algorytmy pakowania bin Karmarkara-Karpa

Karmarkara -Karpa (KK) to kilka powiązanych algorytmów aproksymacji problemu pakowania w pojemniki . Problem pakowania w pojemniki polega na pakowaniu przedmiotów o różnych rozmiarach do pojemników o identycznej pojemności, tak aby całkowita liczba pojemników była jak najmniejsza. Znalezienie optymalnego rozwiązania jest trudne obliczeniowo . Karmarkar i Karp opracowali algorytm, który działa w czasie wielomianowym i znajduje rozwiązanie z co najwyżej ${\ Displaystyle \ operatorname {OPT} + {\ mathcal {O}} (\ log ^ {2} (OPT))}$ pojemniki, gdzie OPT to liczba pojemników w optymalnym rozwiązanie. Opracowali także kilka innych algorytmów z nieco innymi gwarancjami aproksymacji i ograniczeniami czasu wykonywania.

Algorytmy KK uznano za przełom w badaniu pakowania pojemników: znane wcześniej algorytmy znalazły przybliżenie multiplikatywne, w którym liczba pojemników wynosiła co najwyżej r ⋅ O P T + s {\ $OPT} + s}$ dla niektórych stałych ${\ Displaystyle r> 1, s> 0}$ lub co najwyżej ${\ Displaystyle (1+ \ varepsilon) \ operatorname {OPCJA} +1}$ . Algorytmy KK jako pierwsze uzyskały przybliżenie addytywne.

Wejście

Dane wejściowe do problemu pakowania do pojemników to zestaw przedmiotów o różnych rozmiarach, a ₁ ,... a _n . Stosowana jest następująca notacja:

• n - liczba elementów.
• m - liczba różnych rozmiarów przedmiotów. Dla każdego i w 1,..., m :
  • s _i to i -ty rozmiar;
  • n _i to liczba elementów o rozmiarze s _i .
• B - rozmiar pojemnika.

Biorąc pod uwagę instancję I , oznaczamy:

• OPT(I) = optymalne rozwiązanie instancji I .
• FOPT( I ) = ( a ₁ +...+ a _n )/ B = teoretycznie optymalna liczba pojemników, gdy wszystkie pojemniki są całkowicie wypełnione przedmiotami lub ułamkami przedmiotów.

Oczywiście FOPT( I ) ≤OPT(I).

Schemat na wysokim poziomie

Algorytmy KK zasadniczo rozwiązują konfiguracyjny program liniowy :

${\ Displaystyle {\ tekst {minimalizuj}} ~~ \ mathbf {1} \ cdot \ mathbf {x} ~~~ {\ tekst {st}} ~ ~ A \ mathbf {x} \geq \mathbf {n} ~~~{\text{i}}~~\mathbf {x} \geq 0~~~{\text{i}}~~\mathbf {x} ~{ \text{jest liczbą całkowitą}}~}$ .

Tutaj A jest macierzą o m wierszach. Każda kolumna A reprezentuje wykonalną konfigurację - multizbiór rozmiarów pozycji, taki, że suma wszystkich tych rozmiarów wynosi co najwyżej B . Zbiór konfiguracji to C . x jest wektorem o rozmiarze C. Każdy element x _c z x reprezentuje liczbę przypadków użycia konfiguracji c .

• Przykład : załóżmy, że rozmiary przedmiotów to 3,3,3,3,3,4,4,4,4,4, a B = 12. Wtedy jest C = 10 możliwych konfiguracji: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. Macierz A ma dwa wiersze: [4,3,2,2,1,1,1,0,0,0] dla s=3 i [0,0,0,1,0, 1,2,1,2,3] dla s=4. Wektor n to [5,5], ponieważ istnieje 5 elementów każdego rozmiaru. Możliwym optymalnym rozwiązaniem jest x = [1,0,0,0,0,0,1,0,0,1], co odpowiada użyciu trzech pojemników o konfiguracjach 3333, 344, 444.

Istnieją dwie główne trudności w rozwiązaniu tego problemu. Po pierwsze, jest to program liniowy liczb całkowitych , który jest trudny obliczeniowo do rozwiązania. Po drugie, liczba zmiennych to C – liczba konfiguracji, która może być ogromna. Algorytmy KK radzą sobie z tymi trudnościami za pomocą kilku technik, z których część została już wprowadzona przez de-la-Vegę i Luekera. Oto ogólny opis algorytmu (gdzie jest oryginalną instancją): ${\ displaystyle I}$

• 1-a. Niech $będzie$ instancją zbudowaną $elementów$ .
  • 2-a. Niech $będzie$ instancją zbudowaną z grupowania elementów i $grupie$ rozmiaru elementów w każdej grupie do najwyższego elementu w
    • 3-a. Skonstruuj $.$ program liniowy dla , bez ograniczeń integralności
      • 4. Oblicz (ułamkowe) rozwiązanie x dla odprężonego programu liniowego.
    • 3-b. Zaokrąglij x do rozwiązania całkowego dla ${\ displaystyle K}$ .
  • 2-b. „Rozgrupuj” elementy, aby uzyskać rozwiązanie dla ${\ displaystyle J}$ .
• 1b. Dodaj małe elementy, aby uzyskać rozwiązanie dla ${\ displaystyle I}$ .

Poniżej opisujemy po kolei każdy z tych kroków.

Krok 1. Usuwanie i dodawanie małych elementów

Motywacją do usuwania małych przedmiotów jest to, że gdy wszystkie przedmioty są duże, liczba przedmiotów w każdym pojemniku musi być mała, więc liczba możliwych konfiguracji jest (względnie) mała. Wybieramy pewną $wszystkie$$\ cdot B}$ z pierwotnej instancji mniejsze niż $g$ . Niech będzie instancją $wynikową$ Zauważ, że w ${\ displaystyle J}$$elementy$ może zawierać . Pakujemy $.$ opakowanie z $pojemnikami$

Teraz dodajemy małe przedmioty do istniejących pojemników w dowolnej kolejności, o ile jest miejsce. Kiedy w istniejących pojemnikach nie ma już miejsca, otwieramy nowy pojemnik (jak w pakowaniu pojemników z następnym dopasowaniem ). Niech ${\ displaystyle b_ {I}}$ będzie liczbą pojemników w końcowym opakowaniu. Następnie:

${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J}, (1 + 2 g) \ cdot OPT ( ja)+1)}$ .

dowód . Jeśli żadne nowe pojemniki nie zostaną otwarte, liczba pojemników pozostaje ${\ displaystyle b_ {J}}$ . $g$${\ Displaystyle (1-g) \ cdot B \ cdot (b_ {I} -1)}$ całkowity rozmiar co najmniej więc całkowity rozmiar instancji wynosi co najmniej . Dlatego ${\ Displaystyle FOPT \ geq (1-g) \ cdot (b_ {I} -1)}$ , więc optymalne rozwiązanie potrzebuje co najmniej ${\ Displaystyle (1-g) \ cdot (b_ {I} -1)}$ pojemniki. Więc ${\ Displaystyle b_ {I} \ równoważnik OPT / (1-g) + 1 = ( 1+g+g^{2}+\ldots )OPT+1\równoważnik (1+2g)OPT+1}$ . W szczególności, przyjmując g =1/ n , otrzymujemy:

${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J},OPT+2\cdot OPT(I)/n+1)\leq \max(b_{J},OPT+3)}$ ,

ponieważ ${\ Displaystyle OPT (I) \ równoważnik n}$ . Dlatego często przyjmuje się, że wszystkie pozycje są większe niż 1/ n .

Krok 2. Grupowanie i rozgrupowywanie elementów

Motywacją do grupowania elementów jest zmniejszenie liczby różnych rozmiarów elementów, zmniejszenie liczby ograniczeń w konfiguracji LP. Ogólny proces grupowania to:

• Uporządkuj produkty według malejącego rozmiaru.
• Podziel elementy na grupy.
• Dla każdej grupy zmodyfikuj rozmiar wszystkich elementów w grupie do największego rozmiaru w grupie.

Istnieje kilka różnych metod grupowania.

Grupowanie liniowe

Niech ${\ displaystyle k> 1}$ będzie parametrem całkowitym. $Umieść$ największe w grupie 1; kolejne $pozycje$ w grupie 2; i tak dalej (ostatnia grupa może mieć mniej niż $)$ . Niech będzie pierwotną $instancją$ Niech będzie pierwszą grupą (grupą największych elementów) i $K '}$$displaystyle$ $zgrupowana$ instancja pierwszej grupy . Następnie:

• W ${\ displaystyle K'}$ wszystkie elementy mają ten sam rozmiar. W liczba różnych rozmiarów wynosi $\ Displaystyle m (K) \ równoważnik n/k +$$( K.$ .
• ${\ Displaystyle OPT (K) \ równoważnik OPT (J)}$$w$ ponieważ grupa 1 dominuje w grupie 2 $($ wszystkie k pozycji w grupie 1 jest większych niż k pozycji w grupie 2); podobnie grupa 2 w $.$$nad$ grupą 3 itd
• $} -$$k$ możliwe jest spakowanie każdego elementu w jednym pojemniku.

Dlatego ${\ Displaystyle OPT (J) \ leq OPT(K\cup K')\leq OPT(K)+OPT(K')\leq OPT(K)+k}$ . Rzeczywiście, biorąc pod uwagę rozwiązanie { $\ displaystyle$$K$$rozwiązanie$ pojemnikami z najwyżej $.$

Grupowanie geometryczne

Niech ${\ displaystyle k> 1}$ będzie parametrem całkowitym. Grupowanie geometryczne przebiega w dwóch krokach:

• Podziel instancję na kilka instancji $\ displaystyle J_ {r$${\ Displaystyle J_ {0}, J_ {1}, \ ldots}$ tak, aby w każdym przypadku $}$ , wszystkie rozmiary mieszczą się w przedziale ${\ Displaystyle [B/2 ^ {r + 1}, B/2 ^ {r}}}$ . Zauważ, że jeśli wszystkie elementy w ${\ displaystyle J}$$)$ co najmniej wtedy liczba wystąpień wynosi co najwyżej ${\ Displaystyle \ log _ {2} (1 / g$ .
• W każdym przypadku wykonaj zaokrąglenie liniowe z parametrem $r}$$}$ . Niech ${\ Displaystyle K_ {r}, K'_ {r}}$ będą wynikowymi przypadkami. Niech ${\ Displaystyle K: = \ kubek _ {r} K_ {r}}$ i ${\ Displaystyle K': = \ kubek _ {r} K'_ {r}}$ .

Następnie liczba różnych rozmiarów jest ograniczona w następujący sposób:

• dla wszystkich r , ${\ Displaystyle m (K'_ {r}) = 1}$ i ${\ styl wyświetlania m(K_{r})\leq n(J_{r})/(k\cdot 2^{r})+1}$ . $B$ elementy w większe niż ${\ Displaystyle B/2 ^ {r + 1}}$ , mamy ${\ Displaystyle n (J_ {r}) \ równoważnik 2^{r+1}\cdot FOPT(J_{r})}$ , więc ${\ Displaystyle m (K_ {r}) \ równoważnik 2FOPT (J_ {r}) / k + 1}$ . Sumowanie wszystkich r daje ${\ Displaystyle m (K) \ równoważnik 2FOPT (J) / k + \ log _ {2} (1/g)}$ .

Liczba pojemników jest ograniczona w następujący sposób:

• dla wszystkich r , ${\ Displaystyle OPT (K'_ {r}) \ równoważnik k}$ - ponieważ ${\ Displaystyle K'_ {r}}$ ma $2$${\ displaystyle B/2 ^ {r}}$ a wszystkie są mniejsze niż , więc można je zapakować co najwyżej ${\ displaystyle k }$ pojemniki.
• Dlatego ${\ Displaystyle OPT (K ​​') \ równoważnik k \ cdot \ log _ {2} (1 / g)}$ .
• Dlatego ${\ Displaystyle OPT (J) \ równoważnik OPT(K)+OPT(K')\leq OPT(K)+k\cdot \log _{2}(1/g)}$ .

Alternatywne grupowanie geometryczne

Niech ${\ displaystyle k> 1}$ będzie parametrem całkowitym. Uporządkuj produkty według malejącego rozmiaru. Podziel je na grupy w taki sposób, aby całkowity rozmiar w każdej grupie wynosił co najmniej ${\ displaystyle k \ cdot B}$ . Ponieważ rozmiar każdego elementu jest mniejszy niż B , liczba elementów w każdej grupie wynosi co najmniej ${\ displaystyle k + 1}$ . Liczba pozycji w każdej grupie nieznacznie rośnie. Jeśli wszystkie elementy są większe niż ${\ displaystyle g \ cdot B}$ , to liczba elementów w każdej grupie wynosi najwyżej ${\ displaystyle k/g}$ . W każdej grupie tylko większe elementy są zaokrąglane w górę. Można to zrobić tak, że:

• ${\ Displaystyle m (K) \ równoważnik FOPT (J) / k + \ ln (1 / g)}$ .
• ${\ Displaystyle OPT (J) \ równoważnik OPT (K) + 2k \ cdot (2 + \ ln (1/g))}$ .

Krok 3. Konstruowanie LP i zaokrąglanie rozwiązania

Rozważamy konfiguracyjny program liniowy bez ograniczeń integralności:

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

Tutaj możemy użyć ułamkowej liczby każdej konfiguracji.

• 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.

Oznacz optymalne rozwiązanie programu liniowego przez LOPT. Oczywiste są następujące zależności:

• FOPT(I) ≤ LOPT(I), ponieważ FOPT(I) to (prawdopodobnie ułamkowa) liczba pojemników, gdy wszystkie pojemniki są całkowicie wypełnione przedmiotami lub ułamkami przedmiotów. Oczywiście żadne rozwiązanie nie może być bardziej wydajne.
• LOPT(I) ≤ OPT(I), ponieważ LOPT(I) jest rozwiązaniem problemu minimalizacji z mniejszą liczbą ograniczeń.
• OPT(I) < 2*FOPT(I), ponieważ w dowolnym opakowaniu z co najmniej 2 pojemnikami*FOPT(I) suma dwóch najmniej zapełnionych pojemników wynosi co najwyżej B , więc można je połączyć w jeden pojemnik .

Rozwiązanie ułamkowego LP można zaokrąglić do rozwiązania całkowego w następujący sposób.

Załóżmy, że mamy rozwiązanie x dla ułamka LP. Zaokrąglamy x do rozwiązania dla całkowego ILP w następujący sposób.

• Niech x będzie optymalnym podstawowym możliwym rozwiązaniem ułamkowego LP. Załóżmy, że jako $c \ w C} x_ {c} = b_ {L$ { $może$ być liczba ułamkowa). Ponieważ ułamkowy LP ma m ograniczeń (po jednym dla każdego odrębnego rozmiaru), x ma co najwyżej m zmiennych niezerowych, to znaczy co najwyżej m stosowane są różne konfiguracje. Konstruujemy z x opakowanie integralne składające się z części głównej i części szczątkowej .
• Główna część zawiera kosze floor( x _c ) każdej konfiguracji c , dla której x _c > 0.
• Dla części resztkowej (oznaczonej przez R ) konstruujemy dwa opakowania kandydujące:
  • Pojedynczy przedział każdej konfiguracji c , dla której x _c > 0; w sumie potrzebnych jest m pojemników.
  • Pakowanie zachłanne, z mniej niż 2 pojemnikami*FOPT( R ) (ponieważ jeśli są co najmniej 2 pojemniki*FOPT( R ), dwa najmniejsze można połączyć).
• Najmniejsze z tych opakowań wymaga min( m , 2*FOPT( R )) ≤ średnia ( m , 2*FOPT( R )) = FOPT(R) + m /2.
• $do tego$ głównej części daje .
• Czas wykonania tego algorytmu konwersji wynosi O( n log n ).

Oznacza to również, że ${\ Displaystyle OPT (I) \ równoważnik LOPT (I) + m/2}$ .

Krok 4. Rozwiązanie ułamkowego LP

Głównym wyzwaniem w rozwiązaniu ułamkowego LP jest to, że może on mieć ogromną liczbę zmiennych - zmienną dla każdej możliwej konfiguracji.

Podwójny LP

Podwójny program liniowy ułamkowego LP to:

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

Ma m zmiennych ${\ displaystyle y_ {1}, \ ldots, y_ {m}}$ i ograniczenia C - ograniczenie dla każdej konfiguracji. Ma następującą interpretację ekonomiczną. Dla każdego rozmiaru s powinniśmy określić nieujemną cenę ${\ displaystyle y_ {i}}$ . Nasz zysk to łączna cena wszystkich przedmiotów. Chcemy maksymalizować zysk n y z zastrzeżeniem ograniczeń, że łączna cena przedmiotów w każdej konfiguracji wynosi co najwyżej 1. Ten LP ma teraz tylko m zmiennych, ale ogromną liczbę ograniczeń. Nawet wymienienie wszystkich ograniczeń jest niewykonalne.

Na szczęście możliwe jest rozwiązanie problemu z dowolną precyzją bez wymieniania wszystkich ograniczeń, używając wariantu metody elipsoidalnej . Ten wariant otrzymuje jako dane wejściowe wyrocznię separacji : funkcję, która przy danym wektorze y ≥ 0 zwraca jedną z następujących dwóch opcji:

• Twierdź, że y jest wykonalne, to znaczy ${1}}$ ; Lub -
• Twierdź, że y jest niewykonalne i zwróć określone ograniczenie, które zostało naruszone, to znaczy wektor a taki, że za ${\ Displaystyle \ mathbf {a} \ cdot \ mathbf {y} > 1$ .

Metoda elipsoidy zaczyna się od dużej elipsoidy, która zawiera całą wykonalną domenę ${\ Displaystyle A ^ {T} \ mathbf {y} \ równoważnik \ mathbf {1}}$ . Na każdym kroku t bierze środek bieżącej elipsoidy i wysyła go do wyroczni separacji: ${\ displaystyle \ mathbf {y} _ {t}}$

• Jeśli wyrocznia mówi, że $,$ to wykonujemy „cięcie optymalności”: wycinamy z elipsoidy wszystkie punkty y , dla których ${\ Displaystyle \ mathbf {n} \ cdot \ mathbf {y} <\ mathbf {n} \ cdot \ mathbf {y} _ {t}}$ . Te punkty zdecydowanie nie są optymalne.
• Jeśli wyrocznia mówi, że $i$ narusza ograniczenie a , to wykonujemy „cięcie wykonalności”: wycinamy z elipsoidy wszystkie punkty y , dla których ${\ Displaystyle \ mathbf {a} \ cdot \ mathbf {y} > 1}$ . Te punkty są zdecydowanie niewykonalne.

Po wykonaniu cięcia konstruujemy nową, mniejszą elipsoidę. Można wykazać, że proces ten zbiega się do rozwiązania przybliżonego, w czasie wielomianu z wymaganą dokładnością.

Wyrocznia separacji dla podwójnego LP

Dano nam kilka m liczb nieujemnych ${\ Displaystyle y_ {1}, \ ldots, y_ {m}}$ . Musimy zdecydować między dwiema opcjami:

• $;$ możliwej konfiguracji suma tej konfiguracji wynosi co najwyżej 1 oznacza to, że y jest wykonalne.
• Istnieje wykonalna konfiguracja, dla której suma $jest$ 1; oznacza to, że y jest niewykonalne. W takim przypadku również musimy zwrócić konfigurację.

Ten problem można rozwiązać, rozwiązując problem plecakowy , gdzie wartości przedmiotów to ${\ Displaystyle y_ {1}, \ ldots, y_ {m}}$ , wagi przedmiotów to ${\ displaystyle s_ {1}, \ ldots, s_ {m}}$ , a nośność to B (rozmiar pojemnika).

• Jeśli całkowita wartość optymalnego rozwiązania plecakowego wynosi co najwyżej 1, to mówimy, że y jest wykonalne.
• Jeśli całkowita wartość optymalnego rozwiązania plecakowego jest większa niż 1, to mówimy, że y jest niewykonalne, a elementy w optymalnym rozwiązaniu plecakowym odpowiadają konfiguracji, która narusza ograniczenie (ponieważ ${\ displaystyle \ mathbf {a} \cdot \mathbf {y} >1}$ dla wektora a odpowiadającego tej konfiguracji).

$m$ dynamicznego w czasie pseudowielomianowym: to liczba wejść, a to liczba możliwych Aby otrzymać algorytm czasu wielomianowego, możemy w przybliżeniu rozwiązać problem plecakowy, stosując zaokrąglanie danych wejściowych. Załóżmy, że chcemy rozwiązania z tolerancją ${\ displaystyle \ delta}$ . Możemy zaokrąglić każdy z ${\ Displaystyle y_ {1}, \ ldots, y_ {m}}$ w dół do najbliższej wielokrotności ${\ Displaystyle \ delta}$ / n . Wtedy liczba możliwych wartości między 0 a 1 wynosi n / ${\ Displaystyle \ delta}$ , a czas wykonania to ${\ Displaystyle O (mn / \ delta)}$ . Rozwiązaniem jest co najmniej rozwiązanie optymalne minus ${\ displaystyle \ delta}$ / n .

Metoda elipsoidalna z przybliżoną wyrocznią separacji

Metodę elipsoidalną należy dostosować do stosowania przybliżonej wyroczni separacji. Biorąc pod uwagę obecny środek elipsoidy ${\ displaystyle \ mathbf {y} _ {t}}$ :

• Jeśli przybliżona wyrocznia zwróci rozwiązanie o wartości większej niż 1, to $ograniczenie$ niewykonalne, a rozwiązanie odpowiada konfiguracji, która narusza a . Wykonujemy „cięcie wykonalności” w $y$$\ Displaystyle \ mathbf {a} \ cdot \ mathbf { y} >1}$ elipsoidę wszystkie punkty y , dla których .
• $\ mathbf {y} _ {t }}$ rozwiązanie o wartości co najwyżej 1, to może być wykonalne lub nie, ale $displaystyle$ zaokrąglone w dół (oznacz to przez $wykonalne$ . Z definicji zaokrąglenia wiemy, że ${\ Displaystyle \ mathbf {n} \ cdot \ mathbf {z} _ {t} \ geq \ mathbf {n} \ cdot \ mathbf {y} _ {t} - \ mathbf {n} \cdot \mathbf {1} \cdot (\delta /n)=\mathbf {n} \cdot \mathbf {y} _{t}-\delta }$ . Nadal wykonujemy „cięcie optymalności” w $y,$ z elipsoidy wszystkie punkty dla których ${\ Displaystyle \ mathbf {n} \ cdot \ mathbf {y} <\ mathbf {n} \ cdot \ mathbf {y} _ {t}}$ . Zauważ, że $niewykonalne$ , więc jego wartość może być większa niż OPT. Dlatego możemy usunąć niektóre punkty, których cel jest optymalny. Jednak usunięte punkty spełniają ${\ Displaystyle \ mathbf {n} \ cdot \ mathbf {y} <\ mathbf {n} \ cdot \ mathbf {z} _ { t}+\delta \leq {\text{OPCJA}}+\delta }$ ; żaden punkt nie zostanie usunięty, jeśli jego $}$ przekroczy wartość o więcej niż $\ displaystyle \ delta$ .

Korzystanie z przybliżonej wyroczni separacji daje wykonalne rozwiązanie y * dla podwójnego LP, gdzie ${\ Displaystyle \ mathbf {n} \ cdot \ mathbf {y ^ {*}} \ geq LOPT -\ delta }$ , po co najwyżej $iteracjach$ , gdzie $ln (mn / g \ delta) }$ . Całkowity czas działania metody elipsoidalnej z przybliżoną wyrocznią separacji wynosi ${\ Displaystyle O (Qmn / \ delta)}$ .

Eliminacja ograniczeń

Podczas metody elipsoidy używamy co najwyżej ograniczeń Q postaci za ${\ Displaystyle \ mathbf {a} \ cdot \ mathbf {y} \ leq 1$ . Wszystkie inne ograniczenia można wyeliminować, ponieważ nie mają one wpływu na wynik y* metody elipsoidalnej. Możemy wyeliminować jeszcze więcej ograniczeń. Wiadomo, że w każdym LP z m zmiennymi istnieje zbiór m ograniczeń wystarczających do wyznaczenia optymalnego rozwiązania (czyli optymalna wartość jest taka sama, nawet jeśli tylko te m stosowane są ograniczenia). Możemy wielokrotnie uruchamiać metodę elipsoidalną jak powyżej, za każdym razem próbując usunąć określony zestaw ograniczeń. Jeśli wynikowy błąd jest co najwyżej $to$ trwale usuwamy te ograniczenia. Można $_$ _ wynosi co najwyżej ${\ Displaystyle \ około \ delta \ cdot [(Q / m) + m \ ln (Q / m)]}$ . Jeśli spróbujemy zestawów ograniczeń deterministycznie, to w najgorszym przypadku jedna z m prób się powiedzie, więc musimy uruchomić metodę elipsoidy co najwyżej ${\ Displaystyle \ około m \ cdot [(Q / m) + m \ ln (Q / m)] = Q + m ^ {2} \ ln (Q / m )}$ razy. Jeśli wybierzemy ograniczenia do usunięcia losowo, to oczekiwana liczba iteracji to ${\ Displaystyle O (m) \ cdot [1 + \ ln (Q / m)]}$ .

Wreszcie mamy zredukowany podwójny LP, z tylko m zmiennymi i m ograniczeniami. Optymalna wartość zredukowanego LP to $\ w przybliżeniu \delta \cdot [(Q/m)+m\ln(Q/m)]}$$/$ ≈ .

Rozwiązanie pierwotnego LP

Zgodnie z twierdzeniem o dualności LP minimalna wartość pierwotnego LP jest równa maksymalnej wartości podwójnego LP, którą oznaczyliśmy przez LOPT. Gdy mamy zredukowany podwójny LP, bierzemy jego podwójny i bierzemy zredukowany pierwotny LP. Ten LP ma tylko m zmiennych - odpowiadających tylko m z konfiguracji C. Maksymalna wartość zredukowanego podwójnego LP wynosi co najmniej ${\ Displaystyle LOPT-h}$ . Można to pokazać że optymalnym rozwiązaniem zredukowanego pierwotnego LP jest co najwyżej . ${\ Displaystyle LOPT + h}$ . Rozwiązanie zapewnia niemal optymalne pakowanie pojemników przy użyciu maksymalnie m konfiguracji.

Całkowity czas działania algorytmu deterministycznego, gdy wszystkie elementy są większe niż , wynosi: ${\ displaystyle g \ cdot B}$

${\ Displaystyle O \ lewo ({\ Frac {Qmn} {\ delta}} \ cdot (Q + m ^ {2} \ ln {\ Frac {Q}{m}})\right)=O\left({\frac {Q^{2}mn+Qm^{3}n\ln {\frac {Q}{m}}}{\delta } }\right)\około O\left(m^{8}\ln {m}\ln ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\ ln {m}}{h}}\ln({\frac {mn}{gh}})\right)}$ ,

Oczekiwany całkowity czas działania losowego algorytmu to: ${\ Displaystyle O \ left(m^{7}\log {m}\log ^{2}({\frac {mn}{gh}})+{\frac {m^{4}n\log {m}}{h} }\log({\frac {mn}{gh}})\right)}$ .

Algorytmy od końca do końca

Karmarkar i Karp przedstawili trzy algorytmy wykorzystujące powyższe techniki o różnych parametrach. Czas działania wszystkich tych algorytmów zależy od funkcji $która$ jest wielomianową opisującą czas potrzebny do rozwiązania ułamkowego h 1, czyli dla wersji deterministycznej ${\ Displaystyle T (m, n) \ w O (m ^ {8} \ log {m} \ log ^ {2} {n} + m ^ {4 }n\log {m}\log {n})}$ .

Algorytm 1

Niech $.$ stałą reprezentującą pożądaną dokładność

• 1-a. Ustaw sol $\ Displaystyle g = \ max (1/n, \ epsilon / 2)}$ . Niech $będzie$ instancją zbudowaną z $mniejszych$ niż g .
  • 2-a. Ustaw ${\ Displaystyle k = n \ cdot \ epsilon ^ {2}}$ . Niech $będzie$ instancją zbudowaną z $.$$i$ z parametrem k niech pozostałą instancją (grupą k elementów) Zauważ, że ${\ Displaystyle m (K) \ równoważnik n/k + 1 \ około 1 / \ epsilon ^ {2}}$ .
    • 3-a. Skonstruuj $.$ program liniowy dla , bez ograniczeń integralności
      • $1$ Oblicz rozwiązanie x dla , z tolerancją h = . Rezultatem $_$ _ Czas działania to ${\ Displaystyle T (m (K), n (K)} \ równoważnik T (\ epsilon ^ {- 2}, n)}$ .
    • 3-b. Zaokrąglij x do rozwiązania całkowego dla ${\ displaystyle K}$ . Dodaj $_$ najwyżej Całkowita liczba pojemników to ${\ Displaystyle b_ {K} \ równoważnik b_ {L} + m (K) / 2 \ równoważnik LOPT (K) + 1 + 1/2 \ epsilon ^ {2}}$ .
  • 2-b. Zapakuj elementy w ${\ displaystyle K'}$ , używając co najwyżej k pojemników; zdobądź opakowanie ${\ displaystyle J}$ . Liczba pojemników to ${\ Displaystyle b_ {J} \ równoważnik b_ {K} + k \ równoważnik LOPT (K) + 1 + 1/2 \ epsilon ^ {2} + n \ cdot \ epsilon ^ {2}}$ .
• 1b. Dodaj elementy mniejsze niż g $,$ aby uzyskać rozwiązanie . Liczba pojemników to: ${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J}, (1 + 2 g) \ cdot OPT (I) + 1) \ równoważnik (1 + \ epsilon) OPT (I) + 1 / 2\epsilon ^{2}+3}$ .

W sumie liczba pojemników jest w ${\ Displaystyle (1 + \ epsilon) OPT + O (\ epsilon ^ {- 2})}$ i bieg -czas jest w ${\ Displaystyle O (n \ log n + T (\ epsilon ^ {- 2}, n))}$ . Wybierając ${\ Displaystyle \ epsilon = OPCJA ^ {-1/3}}$$Displaystyle OPT + O (OPT ^ {2/3}) }$ P .

Algorytm 2

Niech $0}$$>$ parametrem rzeczywistym, a całkowitym, który zostanie określony później.

• 1-a. Niech $będzie$ instancją zbudowaną z $mniejszych$ niż g .
• 2. Podczas gdy ${\ Displaystyle FOPT (J)> 1 + {\ Frac {k} {k-1}} \ ln (1 /g)}$ wykonaj:
  • 2-a. Wykonaj alternatywne grupowanie geometryczne z parametrem k . Niech $będzie instancją$$wynikową$ i niech instancją Mamy ${\ Displaystyle m (K) \ równoważnik FOPT (J) / k + \ ln (1/g)}$ .
    • 3-a. Skonstruuj $.$ program liniowy dla , bez ograniczeń integralności
      • $1$ Oblicz rozwiązanie x dla , z tolerancją h = . Rezultatem $_$ _ Czas działania to ${\ Displaystyle T (m (K), n (K)} \ równoważnik T (FOPT (J )/k+\ln(1/g),n)}$ .
    • 3-b. Zaokrąglij x do rozwiązania całkowego dla ${\ displaystyle K}$ . Nie dodawaj przedziałów dla części ułamkowej. Zamiast tego po prostu wyjmij spakowane elementy z ${\ displaystyle J}$ .
  • 2-b. $Zapakuj$ elementy do co najwyżej ${\ Displaystyle 2k \ cdot (2+ \ ln (1/g))$ .
• 2. Raz ${\ Displaystyle FOPT (J) \ równoważnik 1 + {\ Frac {k} {k-1}} \ ln ( 1/g)}$ , pozostałe pozycje chciwie spakuj do co najwyżej ${\ Displaystyle 2FOPT (J) \ równoważnik 2 + {\ Frac {2k} {k-1}} \ ln (1 / g)}$ pojemniki.
  • W każdej iteracji pętli w kroku 2 ułamkowa część x ma co najwyżej m ( K ) wzorców, więc ${\ Displaystyle FOPT (J_ {t + 1}) \ równoważnik m (K_ {t}) \ równoważnik FOPT (J_ {t}) / k + \ ln (1 / g)}$ . FOPT spada o współczynnik k w każdej iteracji, więc liczba iteracji wynosi co najwyżej ${\ Displaystyle {\ Frac {\ ln FOPT (I)} {\ ln k}}+1}$ .
  • Dlatego całkowita liczba pojemników używanych $($ : ${\ Displaystyle b_ {J} \ równoważnik OPT (I) + \ lewo [1 + {\ Frac {\ ln FOPT (I)} {\ ln k}} \ prawo]\lewo[1+4k+2k\ln(1/g)\prawo]+2+{\frac {2k}{k-1}}\ln(1/g)}$ .
• 1b. Dodaj elementy mniejsze niż g $,$ aby uzyskać rozwiązanie . Liczba pojemników wynosi: ${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J}, (1+ 2g)\cdot OPT(I)+1)}$ .

Czas wykonania jest w ${\ Displaystyle O (n \ log n + T (FOPT ( J)/k+\ln(1/g),n))}$ .

Teraz, jeśli wybierzemy k = 2 i g = 1/FOPT (I), otrzymamy:

${\ Displaystyle b_ {J} \ równoważnik OPT + O (\ log ^ {2} (FOPT))}$ ,

i stąd:

${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J}, OPT + 2OPT / FOPT + 1) \ równoważnik \ max (b_ {J}, OPT + 5) \ w OPT + \ log ^ {2} (OPT )}$ ,

więc całkowita liczba pojemników wynosi ${\ Displaystyle OPT + O (\ log ^ {2} (FOPT))}$ . Czas wykonania to ${\ Displaystyle O (n \ log n) + T (FOPT / 2 + \ ln (FOPT), n) \ w O (n \ dziennik {n}+T(FOPT,n))}$ .

Ten sam algorytm może być używany z różnymi parametrami, aby uzyskać kompromis między czasem wykonywania a dokładnością. Dla jakiegoś parametru $Displaystyle$ = $^ {\ alfa}$${\ Displaystyle g = 1 / FOPT ^ {1- \ alfa}}$ i . Następnie opakowanie potrzebuje co najwyżej ${\ Displaystyle \ operatorname {OPT} + {\ mathcal {O}} (OPT ^ {\ alfa})}$ , a czas wykonywania jest w ${\ Displaystyle O (n \ log {n} + T (FOPT ^ {(1- \ alfa)}, n))}$ .

Algorytm 3

Trzeci algorytm jest przydatny, gdy liczba rozmiarów m jest mała (patrz także pakowanie bin o dużej wielokrotności ).

• 1-a. Ustaw sol $\ Displaystyle g = {\ Frac {\ log ^ {2} (m)} {FOPT (I)}}}$ . Niech $będzie$ instancją zbudowaną z $mniejszych$ niż g .
• Jeśli ${\ Displaystyle m (K) \ równoważnik FOPT (K)}$ to:
  • 3-a. Skonstruuj $.$ program liniowy dla , bez ograniczeń integralności
    • $1$ Oblicz rozwiązanie x dla , z tolerancją h = . Rezultatem $_$ _ Czas działania to ${\ Displaystyle T (m (K), n (K)} \ równoważnik T (\ epsilon ^ {- 2}, n)}$ .
  • 3-b. Zaokrąglij x do rozwiązania całkowego dla ${\ displaystyle K}$ . Nie dodawaj przedziałów dla części ułamkowej. Zamiast tego po $prostu wyjmij$ elementy z .
• Uruchom krok 2 algorytmu 2 na pozostałych elementach.
• 1-b. Dodaj elementy mniejsze niż g $,$ aby uzyskać rozwiązanie . Liczba pojemników wynosi: ${\ Displaystyle b_ {I} \ równoważnik \ max (b_ {J}, (1+ 2g)\cdot OPT(I)+1)}$ .

Wykorzystuje $_$ _ ${\ Displaystyle O (n \ log {n} + T (m, n))}$ .

Ulepszenia

Techniki KK zostały później ulepszone, aby zapewnić jeszcze lepsze przybliżenia.

Rothvoss używa tego samego schematu co algorytm 2, ale z inną procedurą zaokrąglania w kroku 2. Wprowadził krok „sklejania”, w którym małe elementy są sklejane w celu uzyskania jednego większego elementu. To klejenie można wykorzystać do zwiększenia najmniejszego rozmiaru elementu do około ${\ Displaystyle B / \ log ^ {12} (n)}$ . Gdy wszystkie rozmiary są co najmniej ${\ Displaystyle B / \ log ^ {12} (n)}$ , możemy zastąpić ${\ Displaystyle g = 1 / \ log ^ {12} (n)}$ w gwarancji algorytmu 2 i uzyskaj:

${\ Displaystyle b_ {J} \ równoważnik OPT (I) + O (\ log (FOPT )\log(\log(n)))}$ ,

co daje za ${\ Displaystyle \ operatorname {OPT} + O (\ log (\ operatorname {OPT}) \ cdot \ log \log(\mathrm {OPT} ))}$ pojemniki.

Hoberg i Rothvoss stosują podobny schemat, w którym przedmioty są najpierw pakowane do „kontenerów”, a następnie pojemniki są pakowane do pojemników. Ich $_$ _