Problem z pakowaniem do kosza - Bin packing problem

Pary pokrycie/opakowanie-problemy
Pokrycie problemów Problemy z pakowaniem Minimalna osłona zestawu Maksymalne pakowanie zestawu Minimalna osłona krawędzi Maksymalne dopasowanie Minimalne pokrycie wierzchołków Maksymalny niezależny zestaw Pokrycie kosza Pakowanie na pojemniki Pokrycie wielokąta Opakowanie prostokątne
v T mi

Problemem pakowania bin jest problem optymalizacji , w których elementy o różnych rozmiarach muszą być pakowane w skończonej liczbie pojemników lub pojemników, każdy z danej stałej pojemności, w sposób, który minimalizuje liczbę pojemników używanych. Problem ma wiele zastosowań, takich jak napełnianie kontenerów, ładowanie ciężarówek o ograniczonej wadze, tworzenie kopii zapasowych plików w mediach oraz mapowanie technologii w projektowaniu układów półprzewodnikowych FPGA .

Obliczeniowo, problem jest NP-trudny , a odpowiadający mu problem decyzyjny – decydowanie, czy elementy mogą zmieścić się w określonej liczbie pojemników – jest NP-zupełny . Pomimo najgorszej twardości, optymalne rozwiązania bardzo dużych przypadków problemu można uzyskać za pomocą zaawansowanych algorytmów. Ponadto istnieje wiele algorytmów aproksymacyjnych . Na przykład algorytm pierwszego dopasowania zapewnia szybkie, ale często nieoptymalne rozwiązanie, polegające na umieszczeniu każdego elementu w pierwszym pojemniku, w którym się zmieści. Wymaga czasu Θ ( n  log  n ), gdzie n to liczba elementów do zapakowania. Algorytm może być znacznie skuteczniejszy, najpierw sortując listę elementów w kolejności malejącej (czasami znany jako algorytm malejący według pierwszego dopasowania), chociaż nadal nie gwarantuje to optymalnego rozwiązania, a w przypadku dłuższych list może wydłużyć czas działania algorytm. Wiadomo jednak, że zawsze istnieje przynajmniej jedna kolejność elementów, która pozwala na pierwsze dopasowanie wyprodukować optymalne rozwiązanie.

Istnieje wiele odmian tego problemu, takich jak pakowanie 2D, pakowanie liniowe, pakowanie według wagi, pakowanie według kosztów i tak dalej. Problem pakowania pojemnika może być również postrzegany jako szczególny przypadek problemu z rozkrojonym materiałem . Gdy liczba pojemników jest ograniczona do 1, a każdy przedmiot charakteryzuje się zarówno objętością, jak i wartością, problem maksymalizacji wartości przedmiotów, które mogą zmieścić się w pojemniku, jest znany jako problem plecakowy .

Wariant pakowania do kosza, który występuje w praktyce, polega na tym, że przedmioty mogą dzielić przestrzeń po zapakowaniu do kosza. W szczególności zestaw przedmiotów może zajmować mniej miejsca, gdy są zapakowane razem, niż suma ich indywidualnych rozmiarów. Ten wariant jest znany jako pakowanie maszyn wirtualnych, ponieważ gdy maszyny wirtualne (VM) są pakowane na serwerze, ich całkowite zapotrzebowanie na pamięć może się zmniejszyć ze względu na strony współdzielone przez maszyny wirtualne, które muszą być przechowywane tylko raz. Jeśli przedmioty mogą dzielić przestrzeń w dowolny sposób, problem pakowania do kosza jest trudny do nawet przybliżenia. Jeśli jednak współdzielenie przestrzeni mieści się w hierarchii, jak ma to miejsce w przypadku współdzielenia pamięci w maszynach wirtualnych, problem pakowania pojemnika można skutecznie przybliżyć.

Inny wariant bin pakowania zainteresowania praktyki jest tzw Internecie pakowania bin. Tutaj przedmioty o różnej objętości mają przybywać sekwencyjnie, a decydent musi zdecydować, czy wybrać i spakować aktualnie obserwowany przedmiot, czy też pozwolić mu przejść. Każda decyzja jest nieodwołalna. W przeciwieństwie do tego, pakowanie do kosza w trybie offline pozwala na zmianę kolejności produktów w nadziei na lepsze zapakowanie po przybyciu dodatkowych przedmiotów. To oczywiście wymaga dodatkowego miejsca do przechowywania przedmiotów, które mają być przearanżowane.

Formalne oświadczenie

W Computers and Intractability Garey i Johnson wymieniają problem z pakowaniem pojemników pod odnośnikiem [SR1]. Jego wariant decyzyjny definiują w następujący sposób.

Instancja: skończony zbiór elementów, rozmiar dla każdego , dodatnia liczba całkowita pojemności pojemnika i dodatnia liczba całkowita . ${\ Displaystyle I}$${\ Displaystyle s (i) \ w \ mathbb {Z} ^ {+}}$${\displaystyle ja\w ja}$${\ Displaystyle B}$${\ Displaystyle K}$

Pytanie: Czy istnieje podział na rozłączne zestawy w taki sposób, że suma rozmiarów elementów w każdym z nich jest lub mniejsza? ${\ Displaystyle I}$${\ Displaystyle I_ {1}, \ kropki, I_ {K}}$${\ Displaystyle I_ {j}}$${\ Displaystyle B}$

Należy zauważyć, że w literaturze często stosuje się równoważną notację, gdzie i dla każdego . Ponadto badania są głównie zainteresowane wariantem optymalizacyjnym, który wymaga najmniejszej możliwej wartości . Rozwiązanie jest optymalne, jeśli ma minimalną . Wartość - dla optymalnego rozwiązania dla zbioru pozycji jest oznaczana przez lub tylko wtedy, gdy zbiór pozycji jest jasny z kontekstu. ${\ Displaystyle B = 1}$${\ Displaystyle s (i) \ w \ mathbb {Q} \ czapka (0,1]}$${\displaystyle ja\w ja}$${\ Displaystyle K}$${\ Displaystyle K}$${\ Displaystyle K}$${\ Displaystyle I}$${\ Displaystyle \ operatorname {OPT} (I)}$${\ Displaystyle \ operatorname {OPT}}$

Możliwym sformułowaniem problemu w programowaniu liniowym całkowitoliczbowym jest:

zminimalizować ${\ Displaystyle K = \ suma _ {j = 1} ^ {n} y_ {j}}$
podlega	${\displaystyle K\geq 1,}$
	${\ Displaystyle \ suma _ {i \ w I} ^ {n} s (i) x_ {ij} \ równoważnik By_ {j}}$	${\ Displaystyle \ forall j \ w \ {1, \ ldots, n \}}$
	${\ Displaystyle \ suma _ {j = 1} ^ {n} x_ {ij} = 1,}$	${\displaystyle \forall ja\w ja}$
	${\ Displaystyle y_ {j} \ w \ {0,1 \}}$	${\ Displaystyle \ forall j \ w \ {1, \ ldots, n \}}$
	${\ Displaystyle x_ {ij} \ w \ {0,1 \}}$	${\ Displaystyle \ forall i \ w I \, \ forall j \ w \ {1, \ ldots, n \}}$

gdzie jeśli bin jest używany i czy przedmiot jest umieszczany w bin . ${\ Displaystyle y_ {j} = 1}$${\displaystyle j}$${\displaystyle x_{ij}=1}$${\displaystyle i}$${\displaystyle j}$

Twardość opakowania bin

Problem pakowania pojemnika jest silnie NP-zupełny . Można to udowodnić, sprowadzając problem silnie NP-zupełnych 3 partycji do pakowania w pojemniki.

Co więcej, nie może istnieć algorytm aproksymacji z bezwzględnym współczynnikiem aproksymacji mniejszym niż chyba . Może to zostać potwierdzone przez redukcję z problem podziału : podany wystąpienie strefy, w której suma wszystkich liczb INPUT 2 T konstrukt wystąpienie pojemnika do pakowania, w którym wielkość Bin T . Jeśli istnieje równy podział wejść, to optymalne pakowanie wymaga 2 pojemników; dlatego każdy algorytm ze współczynnikiem aproksymacji mniejszym niż 3/2 musi zwracać mniej niż 3 biny, które muszą być 2 binami. W przeciwieństwie do tego, jeśli nie ma równego podziału wejść, to optymalne pakowanie wymaga co najmniej 3 pojemników. ${\displaystyle 3/2}$${\displaystyle P=NP}$

Z drugiej strony, pakowanie bin można rozwiązać w czasie pseudo-wielomianu dla dowolnej ustalonej liczby bin i rozwiązać w czasie wielomianu dla dowolnej stałej pojemności bin . ${\ Displaystyle K}$${\ Displaystyle B}$

Algorytmy aproksymacyjne do pakowania bin

Aby zmierzyć wydajność algorytmu aproksymacyjnego, w literaturze rozważane są dwa współczynniki aproksymacji. Dla danej listy pozycji liczba oznacza liczbę pojemników użytych przy zastosowaniu algorytmu do listy , natomiast oznacza liczbę optymalną dla tej listy. Bezwzględny stosunek wydajności dla najgorszego przypadku dla algorytmu jest określony jako ${\ Displaystyle L}$${\ Displaystyle A (L)}$${\ Displaystyle A}$${\ Displaystyle L}$${\ Displaystyle \ operatorname {OPT} (L)}$${\ Displaystyle R_ {A}}$${\ Displaystyle A}$

${\ Displaystyle R_ {A} \ równoważnik \ inf \ {r \ geq 1: A (L) / \ operatorname {OPT} (L) \ leq r {\ tekst {dla wszystkich list}} L \}.}$

Z drugiej strony asymptotyczny stosunek najgorszego przypadku definiuje się jako ${\ Displaystyle R_ {A} ^ {\ infty}}$

${\ Displaystyle R_ {A} ^ {\ infty} \ równoważne \ inf \ {r \ geq 1: \ istnieje N> 0, A (L) / \ operatorname {OPT} (L) \ leq r {\ tekst {dla wszystkie listy }}L{\text{ z }}\mathrm {OPT} (L)\geq N\}.}$

Równoważnie jest najmniejszą liczbą taką, że dla pewnej stałej K, dla wszystkich list L:${\ Displaystyle R_ {A} ^ {\ infty}}$

${\ Displaystyle A (L) \ Leq R_ {A} ^ {\ Infty} \ cdot OPT (L) + K}$.

Dodatkowo można ograniczyć listy do tych, dla których wszystkie pozycje mają rozmiar co najwyżej . W przypadku takich list ograniczone wskaźniki wydajności rozmiaru są oznaczone jako i . ${\ Displaystyle \ alfa}$${\ Displaystyle R_ {A} ({\ tekst {rozmiar}} \ leq \ alfa)}$${\ Displaystyle R_ {A} ^ {\ infty} ({\ tekst {rozmiar}} \ leq \ alfa)}$

Algorytmy aproksymacji pakowania pojemników można podzielić na dwie kategorie:

1. Heurystyki online, które rozpatrują pozycje w danej kolejności i umieszczają je jeden po drugim w pojemnikach. Te heurystyki mają również zastosowanie do internetowej wersji tego problemu.
2. Heurystyki offline, które modyfikują podaną listę pozycji np. poprzez sortowanie pozycji według rozmiaru. Algorytmy te nie mają już zastosowania do internetowego wariantu tego problemu. Mają jednak ulepszoną gwarancję aproksymacji, zachowując jednocześnie zaletę małej złożoności czasowej. Podkategorią heurystyk offline są asymptotyczne schematy aproksymacji. Algorytmy te mają gwarancję aproksymacji postaci dla pewnej stałej, od której może zależeć . Dla arbitralnie dużych algorytmy te zbliżają się arbitralnie do . Jednak odbywa się to kosztem (drastycznie) zwiększonej złożoności czasu w porównaniu z podejściami heurystycznymi.${\ Displaystyle (1+ \ varepsilon) \ operatorname {OPT} (L) + C}$${\displaystyle 1/\varepsilon}$${\ Displaystyle \ operatorname {OPT} (L)}$${\ Displaystyle \ operatorname {OPT} (L)}$

Heurystyka online

W wersji online problemu z pakowaniem do kosza przedmioty przychodzą jeden po drugim, a (nieodwracalna) decyzja, gdzie umieścić przedmiot, musi zostać podjęta przed poznaniem następnego przedmiotu lub nawet jeśli będzie następny. Zróżnicowany zestaw heurystyk offline i online dotyczących pakowania w pojemniki został zbadany przez Davida S. Johnsona podczas jego doktoratu. Praca dyplomowa.

Algorytmy jednoklasowe

Istnieje wiele prostych algorytmów, które wykorzystują następujący ogólny schemat:

• Dla każdej pozycji na liście wejściowej:
  1. Jeśli przedmiot pasuje do jednego z aktualnie otwartych pojemników, umieść go w jednym z tych pojemników;
  2. W przeciwnym razie otwórz nowy kosz i włóż do niego nowy przedmiot.

Algorytmy różnią się kryterium, według którego wybierają otwarty pojemnik na nowy przedmiot w kroku 1 (więcej informacji można znaleźć na stronach, do których prowadzą łącza):

• Next Fit (NF) zawsze przechowuje jeden otwarty pojemnik. Gdy nowy przedmiot się do niego nie zmieści, zamyka dotychczasowy pojemnik i otwiera nowy. Jego zaletą jest to, że jest to algorytm o ograniczonej przestrzeni, ponieważ potrzebuje tylko jednego otwartego pojemnika w pamięci. Jego wadą jest to, że jego asymptotyczny stosunek aproksymacji wynosi 2. W szczególności ,, a dla każdegoistnieje listataka, żei. Jego asymptotyczny współczynnik aproksymacji można nieco poprawić w oparciu o rozmiary przedmiotów:dla wszystkichidla wszystkich. Dla każdego algorytmu,który jest algorytmem AnyFit, zawiera to.${\ Displaystyle NF (L) \ leq 2 \ cdot \ operatorname {OPT} (L) -1}$${\ Displaystyle N \ w \ mathbb {N}}$${\ Displaystyle L}$${\ Displaystyle \ operatorname {OPT} (L) = N}$${\ Displaystyle NF (L) = 2 \ cdot \ operatorname {OPT} (L)-2}$${\ Displaystyle R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik 2}$${\ Displaystyle \ alfa \ geq 1/2}$${\ Displaystyle R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik 1 / (1-\ alfa)}$${\ Displaystyle \ alfa \ leq 1/2}$${\ Displaystyle A}$${\ Displaystyle R_ {A} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa)}$
• Next-k-Fit (NkF) jest wariantem Next-Fit, ale zamiast utrzymywać tylko jeden otwarty pojemnik, algorytm utrzymujeotwarteostatniepojemniki i wybiera pierwszy pojemnik, w którym mieści się przedmiot. Dlatego nazywa się toalgorytmem przestrzeni ograniczonej k . PonieważNkF dostarcza wyniki, które są lepsze w porównaniu z wynikami NF, jednak zwiększaniedo stałych wartości większych niżpoprawia algorytm nie dalej w jego najgorszym przypadku. Jeśli algorytmjestalgorytmemPrawieAnyFit, anastępnie.${\displaystyle k}$${\displaystyle k\geq 2}$${\displaystyle k}$${\displaystyle 2}$${\ Displaystyle A}$${\ Displaystyle m = \ l piętro 1 / \ alfa \ r piętro \ geq 2}$${\ Displaystyle R_ {A} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) \ równoważnik R_ {N2F} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) = 1+1/m}$
• Pierwsze dopasowanie (FF) utrzymuje wszystkie pojemniki otwarte w kolejności, w jakiej zostały otwarte. Próbuje umieścić każdy nowy przedmiot w pierwszym pojemniku, do którego pasuje. Jego współczynnik aproksymacji wynosi, a istnieje rodzina list wejściowych,dla którychpasuje do tego ograniczenia.${\ Displaystyle FF (L) \ leq \ l piętro 1,7 \ operatorname {OPT} \ r piętro}$${\ Displaystyle L}$${\ Displaystyle FF (L)}$
• Best-Fit (BF) również utrzymuje wszystkie pojemniki otwarte, ale próbuje umieścić każdy nowy przedmiot w pojemniku z maksymalnym ładunkiem, w jakim pasuje. Jego stosunek aproksymacji jest identyczny jak w przypadku FF, to znaczy:, a istnieje rodzina list wejściowych,dla którychpasuje do tego ograniczenia.${\ Displaystyle BF (L) \ leq \ l piętro 1,7 \ operatorname {OPT} \ r piętro}$${\ Displaystyle L}$${\ Displaystyle BF (L)}$
• Najgorsze dopasowanie (WF) próbuje umieścić każdy nowy przedmiot w koszu przy minimalnym obciążeniu. Może zachowywać się tak źle, jak Next-Fit i zrobi to na liście najgorszych przypadków . Ponadto utrzymuje, że . Ponieważ WF jest algorytmem AnyFit, istnieje algorytm AnyFit taki, że .${\ Displaystyle NF (L) = 2 \ cdot \ operatorname {OPT} (L)-2}$${\ Displaystyle R_ {WF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa) = R_ {NF} ^ {\ infty} ({\ tekst {rozmiar}} \ równoważnik \ alfa)}$${\ Displaystyle R_ {AF} ^ {\ infty} (\ alfa) = R_ {NF} ^ {\ infty} (\ alfa)}$
• Prawie najgorsze dopasowanie (AWF) próbuje umieścić każdy nowy przedmiot w drugim najbardziej pustym otwartym pojemniku (lub najpustszym, jeśli są dwa takie pojemniki). Jeśli nie pasuje, próbuje najbardziej pustego. Ma asymptotyczny stosunek najgorszego przypadku wynoszący .${\ Displaystyle 17/10}$

Aby uogólnić te wyniki, Johnson wprowadził dwie klasy heurystyki online zwane algorytmem dowolnego dopasowania i algorytmem prawie dowolnego dopasowania :

• W algorytmie AnyFit (AF) , jeśli bieżące niepuste pojemniki to B ₁ ,..., B _j , to bieżący element nie zostanie zapakowany do B _j+1, chyba że nie mieści się w żadnym z B ₁ ,.. ., B _j . Algorytmy FF, WF, BF i AWF spełniają ten warunek. Johnson udowodnił, że dla dowolnego algorytmu AnyFit A i dowolnego :${\ Displaystyle \ alfa}$

${\ Displaystyle R_ {FF} ^ {\ infty} (\ alfa) \ leq R_ {A} ^ {\ infty} (\ alfa) \ leq R_ {WF} ^ {\ infty} (\ alfa)}$.

• W algorytmie Prawie Dowolne Dopasowanie (AAF) , jeśli bieżące niepuste pojemniki to B ₁ ,..., B _j , a spośród tych pojemników B _k jest unikalnym pojemnikiem o najmniejszym obciążeniu, to bieżąca pozycja nie zostanie zapakowana do B _k , chyba że nie mieści się w żadnym z pojemników po jego lewej stronie. Algorytmy FF, BF i AWF spełniają ten warunek, ale WF nie. Johnson udowodnił, że dla dowolnego algorytmu AAF A i dowolnego :${\ Displaystyle \ alfa}$

${\ Displaystyle R_ {A} ^ {\ infty} (\ alfa) = R_ {FF} ^ {\ infty} (\ alfa)}$ W szczególności: . ${\ Displaystyle R_ {A} ^ {\ infty} = 1,7}$

Dopracowane algorytmy

Lepsze współczynniki aproksymacji są możliwe w przypadku heurystyk, które nie są AnyFit. Te heurystyki zwykle utrzymują kilka klas otwartych pojemników, poświęconych przedmiotom o różnych rozmiarach (więcej informacji można znaleźć na stronach, do których prowadzą linki):

• Rafinowany-first-fit opakowania bin (RFF) partycje rozmiarów elementu do czterech zakresach:,,, i. Podobnie pojemniki są podzielone na cztery klasy. Następna pozycjajest najpierw przypisywana do odpowiadającej jej klasy. Wewnątrz tej klasy jest przypisywany do kosza za pomocą pierwszego dopasowania . Należy pamiętać, że ten algorytm nie jest algorytmem Any-Fit, ponieważ może otworzyć nowy pojemnik, mimo że bieżący przedmiot mieści się w otwartym pojemniku. Algorytm ten został po raz pierwszy zaprezentowany przez Andrew Chi-Chih Yao, który udowodnił, że ma on gwarancję aproksymacjii przedstawił rodzinę listzfor.${\ Displaystyle (1/2, 1]}$${\ Displaystyle (2/5, 1/2]}$${\ Displaystyle (1/3,2/5]}$${\ Displaystyle (0,1/3]}$${\displaystyle i\wl}$${\ Displaystyle RFF (L) \ leq (5/3) \ cdot \ operatorname {OPT} (L) + 5}$${\ Displaystyle L_ {k}}$${\ Displaystyle RFF (L_ {k}) = (5/3) \ operatorname {OPT} (L_ {k}) + 1/3}$${\ Displaystyle \ operatorname {OPT} (L) = 6k+1}$
• Harmonic-k dzieli przedział rozmiarówna podstawie progresji harmonicznej naczęścidlaitak, że. Algorytm ten został po raz pierwszy opisany przez Lee i Lee. Ma złożoność czasowąi na każdym kroku są co najwyżejotwarte pojemniki, które mogą być potencjalnie wykorzystane do umieszczania przedmiotów, tj. jest toalgorytmzograniczoną przestrzenią. Dla, jego współczynnik aproksymacji spełnia, i jest asymptotycznie ciasny.${\displaystyle (0,1]}$${\ Displaystyle k-1}$${\ Displaystyle I_ {j}: = (1/(j+1), 1/j]}$${\displaystyle 1\leq j<k}$${\ Displaystyle I_ {k}: = (0,1 / k]}$${\ Displaystyle \ bigcup _ {j = 1} ^ {k} I_ {j} = (0,1]}$${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k\rightarrow \infty}$${\ Displaystyle R_ {Hk} ^ {\ infty} \ około 1,6910}$
• Refined-harmonic łączy idee Harmonic-k z pomysłami Refined-First-Fit . Umieszcza przedmioty większe niżpodobne, jak w Refined-First-Fit, podczas gdy mniejsze przedmioty są umieszczane za pomocą Harmonic-k. Intuicja dla tej strategii polega na zmniejszeniu ogromnego marnotrawstwa pojemników zawierających elementy, które są tylko większe niż. Algorytm ten został po raz pierwszy opisany przez Lee i Lee. Udowodnili, że zato się trzyma.${\ Displaystyle 1/3}$${\ Displaystyle 1/2}$${\displaystyle k=20}$${\ Displaystyle R_ {RH} ^ {\ infty} \ równoważnik 373/228}$

Ogólne dolne granice dla algorytmów online

Yao udowodnił w 1980 r., że nie może istnieć algorytm online z asymptotycznym współczynnikiem konkurencji mniejszym niż . Brown i Liang poprawili to przywiązanie do . Później to powiązanie zostało ulepszone przez Vliet. W 2012 r. ta dolna granica została ponownie poprawiona przez Békési i Galambos do . ${\displaystyle 3/2}$${\ Displaystyle 1.53635}$${\ Displaystyle 1,54014}$${\ Displaystyle 248/161\ około 1,54037}$

Tabela porównawcza

Algorytm	Gwarancja zbliżenia	Lista najgorszych przypadków ${\ Displaystyle L}$	Złożoność czasowa
Następne dopasowanie (NF)	${\ Displaystyle NF (L) \ leq 2 \ cdot \ operatorname {OPT} (L) -1}$	${\ Displaystyle NF (L) = 2 \ cdot \ operatorname {OPT} (L)-2}$	${\ Displaystyle {\ mathcal {O}} (| L |)}$
Pierwsze dopasowanie (FF)	${\ Displaystyle FF (L) \ leq \ l piętro 1,7 \ operatorname {OPT} (L) \ r piętro}$	${\ Displaystyle FF (L) = \ l piętro 1,7 \ operatorname {OPT} (L) \ r piętro}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Najlepsze dopasowanie (BF)	${\ Displaystyle BF (L) \ leq \ l piętro 1,7 \ operatorname {OPT} (L) \ r piętro}$	${\ Displaystyle BF (L) = \ l piętro 1,7 \ operatorname {OPT} (L) \ r piętro}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Najgorsze dopasowanie (WF)	${\ Displaystyle WF (L) \ leq 2 \ cdot \ operatorname {OPT} (L) -1}$	${\ Displaystyle WF (L) = 2 \ cdot \ operatorname {OPT} (L)-2}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Prawie najgorsze dopasowanie (AWF)	${\ Displaystyle R_ {AWF} ^ {\ infty} \ równa 17/10}$	${\ Displaystyle R_ {AWF} ^ {\ infty} = 17/10}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Udoskonalone-FirstFit (RFF)	${\ Displaystyle RFF (L) \ leq (5/3) \ cdot \ operatorname {OPT} (L) + 5}$	${\ Displaystyle RFF (L) = (5/3) \ operatorname {OPT} (L) + 1/3}$(dla ) ${\ Displaystyle \ operatorname {OPT} (L) = 6k+1}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Harmoniczne-k (Hk)	${\ Displaystyle R_ {Hk} ^ {\ infty} \ równoważnik 1,69103}$ dla ${\displaystyle k\rightarrow \infty}$	${\ Displaystyle R_ {Hk} ^ {\ infty} \ geq 1,69103}$	${\ Displaystyle {\ mathcal {O}} (| L | \ log (| L |)}$
Wyrafinowane harmoniczne (RH)	${\ Displaystyle R_ {RH} ^ {\ infty} \ leq 373/228 \ około 1,63597}$		${\ Displaystyle {\ mathcal {O}} (| L |)}$
Zmodyfikowane harmoniczne (MH)	${\ Displaystyle R_ {MH} ^ {\ infty} \ leq 538/33 \ około 1,61562}$
Zmodyfikowany harmoniczny 2 (MH2)	${\ Displaystyle R_ {MH2} ^ {\ infty} \ leq 239091/148304 \ około 1,61217}$
Harmoniczne + 1 (H+1)		${\ Displaystyle R_ {H + 1} ^ {\ infty} \ geq 1,59217}$
Harmoniczne ++ (H++)	${\ Displaystyle R_ {H ++} ^ {\ infty} \ leq 1,58889}$	${\ Displaystyle R_ {H ++} ^ {\ infty} \ geq 1,58333}$

Algorytmy offline

W wersji offline pakowania do pojemników algorytm może zobaczyć wszystkie przedmioty przed rozpoczęciem umieszczania ich w pojemnikach. Pozwala to na uzyskanie lepszych wskaźników aproksymacji.

Przybliżenie multiplikatywne

Najprostszą techniką stosowaną przez algorytmy offline jest:

• Porządkowanie listy wejściowej według malejącego rozmiaru;
• Uruchom algorytm online na uporządkowanej liście.

Johnson udowodnił, że każdy algorytm AnyFit A, który działa na liście uporządkowanej według malejącego rozmiaru, ma asymptotyczny stosunek aproksymacji

${\ Displaystyle 1,22 \ około {\ Frac {11}{9}} \ równoważnik R_ {A} ^ {\ infty} \ równoważnik {\ Frac {5} {4}} = 1,25}$.

Niektóre algorytmy z tej rodziny to (więcej informacji na stronach, do których prowadzą linki):

• First-fit-decreasing (FFD) — porządkuje elementy według malejącego rozmiaru, a następnie wywołuje First-Fit. Jego współczynnik aproksymacji wynosi, a to jest ciasne.${\ Displaystyle FFD (I) = 11/9 \ operatorname {OPT} (I) + 6/9}$
• Next-Fit-Decreasing (NFD) — porządkuje elementy według malejącego rozmiaru, a następnie wywołuje funkcję Next-Fit . Jego przybliżony stosunek wynosi w najgorszym przypadku nieco poniżej 1,7. Został również przeanalizowany probabilistycznie. Next-Fit pakuje listę i jej odwrotność do tej samej liczby pojemników. W związku z tym, Next-Fit-Increasing ma taką samą wydajność, jak Next-Fit-Increasing.
• Modified first fit-decreasing (MFFD) - poprawia FFD dla przedmiotów większych niż połowa przedziału, klasyfikując przedmioty według rozmiaru na cztery klasy rozmiarów: duży, średni, mały i mały, odpowiadające przedmiotom o rozmiarze > 1/2 pojemnika, > Odpowiednio 1/3 kosza, > 1/6 kosza i mniejsze przedmioty. Jego gwarancją zbliżenia jest.${\ Displaystyle MFFD (I) \ leq (71/60) \ operatorname {OPT} (I) + 1}$

Fernandez de la Vega i Lueker zaprezentowali PTAS do pakowania w kosze . Dla każdego , ich algorytm znajduje rozwiązanie o co najwyżej rozmiarze i działa w czasie , gdzie oznacza funkcję zależną tylko od . Dla tego algorytmu wymyślili metodę adaptacyjnego zaokrąglania danych wejściowych : liczby wejściowe są grupowane i zaokrąglane w górę do wartości maksimum w każdej grupie. Daje to instancję o niewielkiej liczbie różnych rozmiarów, którą można dokładnie rozwiązać, sprawdzając wszystkie możliwe konfiguracje. ${\ Displaystyle \ varepsilon > 0}$${\ Displaystyle (1+ \ varepsilon ) \ operatorname {OPT} +1}$${\ Displaystyle {\ mathcal {O}} (n \ log (1/\ varepsilon)) + {\ mathcal {O}} _ {\ varepsilon} (1)}$${\ Displaystyle {\ mathcal {O}} _ {\ varepsilon} (1)}$${\displaystyle 1/\varepsilon}$

Przybliżenie addytywne

Karmarkar i Karp przedstawili algorytm z wielomianem czasu wykonywania w i . Ich algorytm znajduje rozwiązanie o rozmiarze co najwyżej . ${\ Displaystyle n}$${\displaystyle 1/\varepsilon}$${\ Displaystyle \ operatorname {OPT} + {\ mathcal {O}} (\ log ^ {2} (OPT))}$

Rothvoss przedstawił algorytm, który generuje rozwiązanie o rozmiarze co najwyżej . ${\ Displaystyle \ operatorname {opcja} + O (\ log (\ operatorname {opcja}) \ cdot \ log \ log (\ operatorname {opcja}})}$

Hoberg i Rothvoss ulepszyli ten algorytm, aby wygenerować rozwiązanie o maksymalnym rozmiarze . Algorytm jest losowy, a czas jego działania jest wielomianem w całkowitej liczbie elementów. ${\ Displaystyle \ operatorname {opcja} + O (\ log (\ operatorname {opcja}}))}$

Tabela porównawcza

Algorytm	Gwarancja zbliżenia	Najgorszy przypadek
Obniżanie według pierwszego dopasowania (FFD)	${\ Displaystyle FFD (I) \ leq 11/9 \ operatorname {OPT} (I) + 6/9}$	${\ Displaystyle FFD (I) = 11/9 \ operatorname {OPT} (I) + 6/9}$
Zmodyfikowane-pierwsze dopasowanie-zmniejszanie (MFFD)	${\ Displaystyle MFFD (I) \ leq (71/60) \ operatorname {OPT} (I) + 1}$	${\ Displaystyle R_ {MFFD} ^ {\ infty} \ geq 71/60}$
Karmarkar i Karp	${\ Displaystyle KK (I) \ Leq OPT (I) + O (\ log ^ {2} {OPT (I)})}$
Rothvoss	${\ Displaystyle HB (I) \ Leq OPT (I) + O (\ log {OPT (I)} \ log \ log {OPT (I)})}$
Hoberg i Rothvoss	${\ Displaystyle HB (I) \ Leq OPT (I) + O (\ log {OPT (I)})}$

Dokładne algorytmy

Martello i Toth opracowali dokładny algorytm dla problemu pakowania jednowymiarowego, zwanego MTP. Szybszą alternatywą jest algorytm Bin Completion zaproponowany przez Korfa w 2002 roku, a później ulepszony.

Kolejne ulepszenie zostało przedstawione przez Schreibera i Korfa w 2013 roku. Nowy algorytm Ulepszonego uzupełniania pojemnika jest nawet o pięć rzędów wielkości szybszy niż uzupełnianie pojemnika w przypadku nietrywialnych problemów z 100 pozycjami i przewyższa BCP (branch-and- cut-and-price) Belov i Scheithauer w problemach, które mają mniej niż 20 pojemników jako optymalne rozwiązanie. Który algorytm działa najlepiej, zależy od właściwości problemu, takich jak liczba elementów, optymalna liczba pojemników, niewykorzystana przestrzeń w optymalnym rozwiązaniu i precyzja wartości.

Goemans i Rothvoss przedstawili algorytm pakowania pojemników z d różnymi rozmiarami przedmiotów, gdzie może być wiele przedmiotów o każdym rozmiarze. Ich algorytm jest wielomianowy, gdy d jest stałe, a wszystkie liczby są podane w kodowaniu binarnym.

Pakowanie w pojemnikach z ograniczeniami kardynalności

Istnieje wariant pakowania pojemników, w którym istnieją ograniczenia kardynalności pojemników: każdy pojemnik może zawierać maksymalnie k pozycji, dla pewnej stałej liczby całkowitej k .

• Krause, Shen i Schwetman przedstawiają ten problem jako wariant optymalnego planowania zadań : komputer ma kilka k procesorów. Istnieje kilka n zadań, które zajmują jednostkę czasu (1), ale mają inne wymagania dotyczące pamięci. Każda jednostka czasu jest traktowana jako pojedynczy pojemnik. Celem jest użycie jak najmniejszej liczby pojemników (=jednostek czasu), przy jednoczesnym zapewnieniu, że w każdym pojemniku zostanie uruchomionych co najwyżej k zadań. Przedstawiają kilka algorytmów heurystycznych, które znajdują rozwiązanie z co najwyżej binami.${\displaystyle 2OPT}$
• Kellerer i Pferschy przedstawiają algorytm z run-time , który znajduje rozwiązanie z co najwyżej binami. Ich algorytm wykonuje wyszukiwanie binarne dla OPT. Dla każdej wyszukanej wartości m próbuje zapakować przedmioty do 3 m /2 pojemników.${\ Displaystyle O (n ^ {2} \ log {n})}$${\displaystyle \lceil {\frac {3}{2}}\mathrm {OPT} \rceil}$

Powiązane problemy

W problemie pakowania pojemników rozmiar pojemników jest stały, a ich liczba może być powiększona (ale powinna być jak najmniejsza).

W przeciwieństwie do tego, w problemie wielokierunkowego partycjonowania liczb , liczba pojemników jest stała, a ich rozmiar można powiększyć. Celem jest znalezienie partycji, w której rozmiary pojemników są tak prawie równe, jak to tylko możliwe (w wariancie zwanym problemem planowania wieloprocesorowego lub problemem minimalnego zakresu , celem jest w szczególności zminimalizowanie rozmiaru największego pojemnika).

W przypadku problemu z odwróconym pakowaniem pojemników zarówno liczba pojemników, jak i ich rozmiary są stałe, ale rozmiary elementów można zmienić. Celem jest osiągnięcie minimalnych zakłóceń wektora rozmiaru elementu, tak aby wszystkie elementy można było zapakować do określonej liczby pojemników.

W przypadku problemu z maksymalnym pakowaniem pojemników celem jest maksymalizacja liczby używanych pojemników, tak aby przy pewnym zamówieniu pojemników żaden element z późniejszego pojemnika nie pasował do wcześniejszego pojemnika. W podwójnym problemie liczba pojemników jest stała, a celem jest zminimalizowanie całkowitej liczby lub całkowitego rozmiaru przedmiotów umieszczanych w pojemnikach, tak aby żaden pozostały przedmiot nie mieścił się w niewypełnionym pojemniku.

W zagadnieniu pokrywania pojemników rozmiar pojemnika jest ograniczony od dołu : celem jest maksymalizacja liczby używanych pojemników tak, aby całkowity rozmiar w każdym pojemniku był co najmniej określony próg.

W problemie sprawiedliwej niepodzielnej alokacji obowiązków (wariant sprawiedliwej alokacji przedmiotów ) przedmioty reprezentują obowiązki i są różne osoby, z których każda przypisuje inną wartość trudności każdemu obowiązkowi. Celem jest przydzielenie każdej osobie zestawu obowiązków z górną granicą całkowitej wartości trudności (w ten sposób każda osoba odpowiada koszowi). W tym problemie stosuje się również wiele technik pakowania w pojemniki.

W problemie cięcia gilotynowego zarówno przedmioty, jak i „pojemniki” są dwuwymiarowymi prostokątami, a nie jednowymiarowymi liczbami, a przedmioty muszą być wycinane z pojemnika za pomocą cięć od końca do końca.

W egoistycznym problemie pakowania do kosza każdy przedmiot to gracz, który chce zminimalizować jego koszt.

Istnieje również wariant pakowania koszowego, w którym kosztem, który należy zminimalizować, nie jest liczba koszy, ale pewna funkcja wklęsła liczby sztuk w każdym koszu.

Inne warianty są dwuwymiarowe pakowania bin, trójwymiarowy pakowania bin , bin packing z dostawą ,

Realizacje

• Online : wizualizacja heurystyk dla pakowania bin 1D i 2D
• Python: pakiet binpacking zawiera algorytmy zachłanne na rozwiązanie dwóch problemów pakowania typowy BIN: (I) do pakowania produktów w stałej liczby pojemników, (ii) pakowanie elementów do małej liczby pojemników o stałym rozmiarze.
• C++ : Pakiet bin-packing zawiera różne zachłanne algorytmy, a także dane testowe.
• Pakiet OR-tools zawiera algorytmy pakowania bin w C++, z wrapperami w Pythonie, C# i Javie.
• C : Implementacja 7 klasycznych algorytmów przybliżonego pakowania bin w C z wynikami i obrazami
• PHP : klasa PHP do pakowania plików bez przekraczania określonego limitu rozmiaru
• Haskell : Implementacja kilku heurystyk pakowania bin , w tym FFD i MFFD.
• C : Fpart : narzędzie wiersza poleceń typu open source do pakowania plików (na licencji C, BSD)
• C# : Solver do pakowania i cięcia pojemników
• Java : caparf - Cutting And Packing Algorithms Research Framework , w tym szereg algorytmów pakowania bin i danych testowych.

Bibliografia