Problemă de ambalare a coșului - Bin packing problem

Perechi de acoperire / ambalare-problemă
Probleme de acoperire Probleme de ambalare Capac minim setat Ambalare setată maximă Capac minim de margine Potrivire maximă Capac minim de vârf Set independent maxim Acoperire coș Ambalare coș Acoperire poligon Ambalare dreptunghiulară
v t e

Problema de ambalare a coșurilor este o problemă de optimizare , în care articolele de diferite dimensiuni trebuie să fie ambalate într-un număr finit de coșuri sau containere, fiecare cu o capacitate dată fixă, într-un mod care să minimizeze numărul de coșuri utilizate. Problema are multe aplicații, cum ar fi umplerea containerelor, încărcarea camioanelor cu constrângeri de capacitate de greutate, crearea copiilor de rezervă ale fișierelor în medii și cartografierea tehnologiei în proiectarea cipurilor semiconductoare FPGA .

Computațional, problema este NP-hard , iar problema de decizie corespunzătoare - a decide dacă articolele se pot încadra într-un număr specificat de pubele - este NP-completă . În ciuda durității sale în cel mai rău caz, soluții optime pentru cazuri foarte mari ale problemei pot fi produse cu algoritmi sofisticati. În plus, există mulți algoritmi de aproximare . De exemplu, primul algoritm de potrivire oferă o soluție rapidă, dar adesea non-optimă, implicând plasarea fiecărui element în primul coș în care se va încadra. Necesită timp Θ ( n  jurnal  n ), unde n este numărul de articole care trebuie ambalate. Algoritmul poate fi mult mai eficient sortând mai întâi lista articolelor în ordine descrescătoare (uneori cunoscut sub numele de algoritm descrescător de primă potrivire), deși acest lucru nu garantează încă o soluție optimă, iar pentru liste mai lungi poate crește timpul de funcționare a algoritmul. Se știe, totuși, că există întotdeauna cel puțin o comandă de articole care permite prima potrivire să producă o soluție optimă.

Există multe variante ale acestei probleme, cum ar fi ambalarea 2D, ambalarea liniară, ambalarea în greutate, ambalarea în funcție de cost și așa mai departe. Problema ambalării coșului poate fi văzută și ca un caz special al problemei materialului tăietor . Atunci când numărul de coșuri este limitat la 1 și fiecare articol este caracterizat atât de un volum, cât și de o valoare, problema maximizării valorii articolelor care se pot potrivi în coș este cunoscută sub numele de problema rucsacului .

O variantă de ambalare a coșurilor care apare în practică este atunci când articolele pot împărți spațiu atunci când sunt ambalate într-un coș. Mai exact, un set de articole ar putea ocupa mai puțin spațiu atunci când sunt ambalate împreună decât suma dimensiunilor lor individuale. Această variantă este cunoscută sub numele de împachetare VM, deoarece atunci când mașinile virtuale (VM) sunt ambalate într-un server, cerința lor totală de memorie ar putea scădea din cauza paginilor partajate de VM-urile care trebuie stocate o singură dată. Dacă articolele pot împărți spațiu în moduri arbitrare, problema ambalării coșului este greu de aproximat. Cu toate acestea, dacă partajarea spațiului se încadrează într-o ierarhie, la fel ca în cazul partajării de memorie în mașinile virtuale, problema de împachetare a coșului poate fi aproximată eficient.

O altă variantă de ambalare a coșurilor de interes în practică este așa-numitul ambalare a coșurilor online . Aici articolele de volum diferit ar trebui să ajungă secvențial, iar factorul de decizie trebuie să decidă dacă să selecteze și să împacheteze elementul observat în prezent sau să îl lase să treacă. Fiecare decizie este fără rechemare. În schimb, ambalarea offline a coșurilor permite rearanjarea articolelor în speranța de a realiza o ambalare mai bună odată cu sosirea articolelor suplimentare. Desigur, acest lucru necesită spațiu de stocare suplimentar pentru păstrarea obiectelor care urmează să fie rearanjate.

Declarație formală

În Computers and Intractability, Garey și Johnson enumeră problema ambalării coșurilor sub referința [SR1]. Ei definesc varianta de decizie după cum urmează.

Instanță: Set finit de articole, o dimensiune pentru fiecare , o capacitate pozitivă a coșului întreg și un număr întreg pozitiv . ${\ displaystyle I}$${\ displaystyle s (i) \ in \ mathbb {Z} ^ {+}}$${\ displaystyle i \ in I}$${\ displaystyle B}$${\ displaystyle K}$

Întrebare: Există o partiție din seturi disjuncte astfel încât suma dimensiunilor articolelor din fiecare să fie sau mai mică? ${\ displaystyle I}$${\ displaystyle I_ {1}, \ dots, I_ {K}}$${\ displaystyle I_ {j}}$${\ displaystyle B}$

Rețineți că în literatură se folosește adesea o notație echivalentă, unde și pentru fiecare . În plus, cercetarea este în mare parte interesată de varianta de optimizare, care cere cea mai mică valoare posibilă a . O soluție este optimă dacă are minim . - Valoare pentru o soluție optimă pentru un set de elemente este notat cu sau doar în cazul în care setul de elemente este clar din context. ${\ displaystyle B = 1}$${\ displaystyle s (i) \ in \ mathbb {Q} \ cap (0,1]}$${\ displaystyle i \ in I}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle I}$${\ displaystyle \ mathrm {OPT} (I)}$${\ displaystyle \ mathrm {OPT}}$

O posibilă formulare a programării liniare întregi a problemei este:

minimiza ${\ displaystyle K = \ sum _ {j = 1} ^ {n} y_ {j}}$
supus	${\ displaystyle K \ geq 1,}$
	${\ displaystyle \ sum _ {i \ in I} ^ {n} s (i) x_ {ij} \ leq By_ {j},}$	${\ displaystyle \ forall j \ in \ {1, \ ldots, n \}}$
	${\ displaystyle \ sum _ {j = 1} ^ {n} x_ {ij} = 1,}$	${\ displaystyle \ forall i \ in I}$
	${\ displaystyle y_ {j} \ in \ {0,1 \},}$	${\ displaystyle \ forall j \ in \ {1, \ ldots, n \}}$
	${\ displaystyle x_ {ij} \ in \ {0,1 \},}$	${\ displaystyle \ forall i \ in I \, \ forall j \ in \ {1, \ ldots, n \}}$

unde se folosește coșul și dacă elementul este pus în coș . ${\ displaystyle y_ {j} = 1}$${\ displaystyle j}$${\ displaystyle x_ {ij} = 1}$${\ displaystyle i}$${\ displaystyle j}$

Duritatea ambalării coșului

Problema ambalării coșului este complet NP-completă . Acest lucru poate fi dovedit prin reducerea puternică a problemei cu 3 partiții NP-complete la ambalarea coșului.

Mai mult, nu poate exista un algoritm de aproximare cu un raport de aproximare absolut mai mic decât dacă . Acest lucru poate fi demonstrat printr - o reducere de problema partiție : dat o instanță de partiție în cazul în care suma tuturor numerelor de intrare este de 2 T , construi un exemplu de-bin de ambalare , în care dimensiunea bin este T . Dacă există o partiție egală a intrărilor, atunci ambalarea optimă are nevoie de 2 coșuri; prin urmare, fiecare algoritm cu raport de aproximare mai mic de 3/2 trebuie să returneze mai puțin de 3 coșuri, care trebuie să fie 2 coșuri. În schimb, dacă nu există o partiție egală a intrărilor, atunci ambalarea optimă are nevoie de cel puțin 3 coșuri. ${\ displaystyle 3/2}$${\ displaystyle P = NP}$

Pe de altă parte, ambalarea coșurilor este rezolvabilă în timp pseudo-polinomial pentru orice număr fix de coșuri și rezolvabilă în timp polinomial pentru orice capacitate fixă ​​a coșului . ${\ displaystyle K}$${\ displaystyle B}$

Algoritmi de aproximare pentru ambalarea coșurilor

Pentru a măsura performanța unui algoritm de aproximare există două rapoarte de aproximare luate în considerare în literatură. Pentru o listă dată de elemente , numărul indică numărul de pubele utilizate atunci când algoritmul este aplicat listei , în timp ce indică numărul optim pentru această listă. Raportul de performanță cel mai rău caz pentru un algoritm este definit ca ${\ displaystyle L}$${\ displaystyle A (L)}$${\ displaystyle A}$${\ displaystyle L}$${\ displaystyle \ mathrm {OPT} (L)}$${\ displaystyle R_ {A}}$${\ displaystyle A}$

${\ displaystyle R_ {A} \ equiv \ inf \ {r \ geq 1: A (L) / \ mathrm {OPT} (L) \ leq r {\ text {pentru toate listele}} L \}.}$

Pe de altă parte, raportul asimptotic în cel mai rău caz este definit ca ${\ displaystyle R_ {A} ^ {\ infty}}$

${\ displaystyle R_ {A} ^ {\ infty} \ equiv \ inf \ {r \ geq 1: \ există N> 0, A (L) / \ mathrm {OPT} (L) \ leq r {\ text {pentru toate listele}} L {\ text {cu}} \ mathrm {OPT} (L) \ geq N \}.}$

În mod echivalent, este cel mai mic număr astfel încât, pentru o constantă K, pentru toate listele L:${\ displaystyle R_ {A} ^ {\ infty}}$

${\ displaystyle A (L) \ leq R_ {A} ^ {\ infty} \ cdot OPT (L) + K}$.

În plus, se pot restricționa listele la cele pentru care toate articolele au o dimensiune de cel mult . Pentru astfel de liste, raporturile de performanță ale mărimii delimitate sunt notate ca și . ${\ displaystyle \ alpha}$${\ displaystyle R_ {A} ({\ text {size}} \ leq \ alpha)}$${\ displaystyle R_ {A} ^ {\ infty} ({\ text {size}} \ leq \ alpha)}$

Algoritmii de aproximare pentru ambalarea coșurilor pot fi clasificate în două categorii:

1. Euristică online, care ia în considerare articolele într-o anumită ordine și le plasează unul câte unul în coșuri. Aceste euristici sunt aplicabile și versiunii online a acestei probleme.
2. Euristică offline, care modifică lista dată de articole, de exemplu prin sortarea articolelor după mărime. Acești algoritmi nu mai sunt aplicabili variantei online a acestei probleme. Cu toate acestea, acestea au o garanție de aproximare îmbunătățită, menținând în același timp avantajul complexității lor de timp reduse. O subcategorie de euristici offline sunt schemele de aproximare asimptotice. Acești algoritmi au o garanție de aproximare a formei pentru o constantă care poate depinde . Pentru un arbitrar mare, acești algoritmi se apropie în mod arbitrar . Cu toate acestea, acest lucru este costat cu o complexitate de timp (drastic) crescută în comparație cu abordările euristice.${\ displaystyle (1+ \ varepsilon) \ mathrm {OPT} (L) + C}$${\ displaystyle 1 / \ varepsilon}$${\ displaystyle \ mathrm {OPT} (L)}$${\ displaystyle \ mathrm {OPT} (L)}$

Euristică online

În versiunea online a problemei de ambalare a coșurilor, articolele sosesc unul după altul și trebuie luată decizia (ireversibilă) unde trebuie plasat un articol înainte de a cunoaște următorul articol sau chiar dacă va exista altul. Un set divers de euristici offline și online pentru ambalarea a coșurilor au fost studiate de David S. Johnson pe doctoratul său. teză.

Algoritmi de clasă unică

Există mulți algoritmi simpli care utilizează următoarea schemă generală:

• Pentru fiecare element din lista de introducere:
  1. Dacă elementul se potrivește într-unul dintre coșurile deschise în prezent, puneți-l într-unul dintre aceste coșuri;
  2. În caz contrar, deschideți un coș nou și puneți noul element în el.

Algoritmii diferă în ceea ce privește criteriul prin care aleg coșul deschis pentru noul articol la pasul 1 (consultați paginile legate pentru mai multe informații):

• Next Fit (NF) păstrează întotdeauna un singur coș deschis. Când noul articol nu se încadrează în el, acesta închide coșul curent și deschide un coș nou. Avantajul său este că este un algoritm de spațiu delimitat, deoarece trebuie doar să păstreze un singur coș deschis în memorie. Dezavantajul său este că raportul său de aproximare asimptotică este 2. În special,, și pentru fiecareexistă o listăastfel încâtși. Raportul său de aproximare asimptotică poate fi oarecum îmbunătățit pe baza dimensiunilor articolelor:pentru toțișipentru toți. Pentru fiecare algoritmcare este un algoritm AnyFit, acesta reține că.${\ displaystyle NF (L) \ leq 2 \ cdot \ mathrm {OPT} (L) -1}$${\ displaystyle N \ in \ mathbb {N}}$${\ displaystyle L}$${\ displaystyle \ mathrm {OPT} (L) = N}$${\ displaystyle NF (L) = 2 \ cdot \ mathrm {OPT} (L) -2}$${\ displaystyle R_ {NF} ^ {\ infty} ({\ text {size}} \ leq \ alpha) \ leq 2}$${\ displaystyle \ alpha \ geq 1/2}$${\ displaystyle R_ {NF} ^ {\ infty} ({\ text {size}} \ leq \ alpha) \ leq 1 / (1- \ alpha)}$${\ displaystyle \ alpha \ leq 1/2}$${\ displaystyle A}$${\ displaystyle R_ {A} ^ {\ infty} ({\ text {size}} \ leq \ alpha) \ leq R_ {NF} ^ {\ infty} ({\ text {size}} \ leq \ alpha)}$
• Next-k-Fit (NkF) este o variantă a Next-Fit, dar în loc să păstreze doar un singur coș deschis, algoritmul menține ultimelecoșuri deschise și alege primul coș în care se încadrează articolul. Prin urmare, se numeștealgoritm de spațiu limitat cu k . Pentrucă NkF oferă rezultate care sunt îmbunătățite comparativ cu rezultatele NF, totuși, creștereala valori constante mai mari decâtîmbunătățește algoritmul nu mai departe în cel mai rău comportament al său. Dacă algoritmuleste unalgoritmAlmostAnyFit șiapoi.${\ displaystyle k}$${\ displaystyle k \ geq 2}$${\ displaystyle k}$${\ displaystyle 2}$${\ displaystyle A}$${\ displaystyle m = \ lfloor 1 / \ alpha \ rfloor \ geq 2}$${\ displaystyle R_ {A} ^ {\ infty} ({\ text {size}} \ leq \ alpha) \ leq R_ {N2F} ^ {\ infty} ({\ text {size}} \ leq \ alpha) = 1 + 1 / m}$
• First-Fit (FF) menține toate coșurile deschise, în ordinea în care au fost deschise. Încearcă să plaseze fiecare element nou în primul coș în care se potrivește. Raportul său de aproximare esteși există o familie de liste de intrarepentru care sepotrivește cu această legătură.${\ displaystyle FF (L) \ leq \ lfloor 1.7 \ mathrm {OPT} \ rfloor}$${\ displaystyle L}$${\ displaystyle FF (L)}$
• Best-Fit (BF) , de asemenea, menține toate coșurile deschise, dar încearcă să plaseze fiecare articol nou în coș cusarcina maximă în care se potrivește. Raportul său de aproximare este idenetic cu cel al FF, adică:,și există o familie de liste de intrarepentru care sepotrivește cu această legătură.${\ displaystyle BF (L) \ leq \ lfloor 1.7 \ mathrm {OPT} \ rfloor}$${\ displaystyle L}$${\ displaystyle BF (L)}$
• Worst-Fit (WF) încearcă să plaseze fiecare articol nou în coș cu sarcina minimă . Se poate comporta la fel de prost ca Next-Fit și va face acest lucru în lista celor mai nefavorabile . Mai mult, susține că . Deoarece WF este un algoritm AnyFit, există un algoritm AnyFit astfel încât .${\ displaystyle NF (L) = 2 \ cdot \ mathrm {OPT} (L) -2}$${\ displaystyle R_ {WF} ^ {\ infty} ({\ text {size}} \ leq \ alpha) = R_ {NF} ^ {\ infty} ({\ text {size}} \ leq \ alpha)}$${\ displaystyle R_ {AF} ^ {\ infty} (\ alpha) = R_ {NF} ^ {\ infty} (\ alpha)}$
• Aproape Worst-Fit (AWF) încearcă să plaseze fiecare element nou în interiorul celui de- al doilea coș deschis cel mai gol (sau cel mai gol coș dacă există două astfel de coșuri). Dacă nu se potrivește, o încearcă pe cea mai goală. Are un raport asimptotic în cel mai rău caz .${\ displaystyle 17/10}$

Pentru a generaliza aceste rezultate, Johnson a introdus două clase de euristici online numite algoritm de potrivire oricărui algoritm și aproape orice potrivire :

• Într - un AnyFit (AF) algoritm, în cazul în lăzile nevide actuale sunt B ₁ , ..., B _j , atunci elementul curent nu va fi ambalat în B _{j + 1} cu excepția cazului în care nu se încadrează în niciuna dintre B ₁ , .. ., B _j . Algoritmii FF, WF, BF și AWF îndeplinesc această condiție. Johnson a dovedit că, pentru orice algoritm AnyFit A și orice :${\ displaystyle \ alpha}$

${\ displaystyle R_ {FF} ^ {\ infty} (\ alpha) \ leq R_ {A} ^ {\ infty} (\ alpha) \ leq R_ {WF} ^ {\ infty} (\ alpha)}$.

• Într-un algoritm AlmostAnyFit (AAF) , în cazul în care coșurile neocupate actuale sunt B ₁ , ..., B _j , iar dintre aceste coșuri, B _k este coșul unic cu cea mai mică sarcină, atunci elementul curent nu va fi ambalat în B _k , cu excepția cazului în care nu se încadrează în niciunul dintre coșurile din stânga sa. Algoritmii FF, BF și AWF îndeplinesc această condiție, dar WF nu. Johnson a demonstrat că, pentru orice algoritm AAF A și orice :${\ displaystyle \ alpha}$

${\ displaystyle R_ {A} ^ {\ infty} (\ alpha) = R_ {FF} ^ {\ infty} (\ alpha)}$ În special: . ${\ displaystyle R_ {A} ^ {\ infty} = 1.7}$

Algoritmi rafinați

Rapoarte de aproximare mai bune sunt posibile cu euristicile care nu sunt AnyFit. Aceste euristici păstrează de obicei mai multe clase de pubele deschise, dedicate articolelor de diferite mărimi (vezi paginile legate pentru mai multe informații):

• Rafinat-prima-fit ambalare bin (RFF) partitiilor Dimensiunile elementului în patru intervale:,,și. În mod similar, coșurile sunt clasificate în patru clase. Următorul articoleste atribuit mai întâi clasei sale corespunzătoare. În interiorul acelei clase, este atribuit unui coș folosind prima potrivire . Rețineți că acest algoritm nu este un algoritm Any-Fit, deoarece poate deschide un coș nou, în ciuda faptului că elementul curent se potrivește într-un coș deschis. Acest algoritm a fost prezentat pentru prima dată de Andrew Chi-Chih Yao, care a dovedit că are o garanție de aproximareși a prezentat o familie de listecufor.${\ displaystyle (1 / 2,1]}$${\ displaystyle (2 / 5,1 / 2]}$${\ displaystyle (1 / 3,2 / 5]}$${\ displaystyle (0,1 / 3]}$${\ displaystyle i \ în L}$${\ displaystyle RFF (L) \ leq (5/3) \ cdot \ mathrm {OPT} (L) +5}$${\ displaystyle L_ {k}}$${\ displaystyle RFF (L_ {k}) = (5/3) \ mathrm {OPT} (L_ {k}) + 1/3}$${\ displaystyle \ mathrm {OPT} (L) = 6k + 1}$
• Harmonic-k partiționează intervalul de dimensiunibazat pe o progresie armonică înbucățipentrușiastfel încât. Acest algoritm a fost descris pentru prima dată de Lee și Lee. Are o complexitate de timpși, la fiecare pas, există cel multpubele deschise care pot fi utilizate potențial pentru plasarea articolelor, adică este unalgoritm spațial limitat. Deoarece, raportul său de aproximare este satisfăcutși este asimptotic strâns.${\ 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} \ approx 1.6910}$
• Refined-harmonic combină ideile de la Harmonic-k cu ideile de la Refined-First-Fit . Plasează obiectele mai mari decâtsimilare ca în Refined-First-Fit, în timp ce obiectele mai mici sunt plasate folosind Harmonic-k. Intuiția pentru această strategie este de a reduce deșeurile uriașe pentru coșurile care conțin bucăți care sunt doar mai mari decât. Acest algoritm a fost descris pentru prima dată de Lee și Lee. Ei au dovedit că pentruasta susține că.${\ displaystyle 1/3}$${\ displaystyle 1/2}$${\ displaystyle k = 20}$${\ displaystyle R_ {RH} ^ {\ infty} \ leq 373/228}$

Limite generale generale pentru algoritmii online

Yao a dovedit în 1980 că nu poate exista un algoritm online cu un raport competitiv asimptotic mai mic decât . Brown și Liang au îmbunătățit această legătură cu . Ulterior, această legătură a fost îmbunătățită până la Vliet. În 2012, această limită inferioară a fost din nou îmbunătățită de Békési și Galambos până la . ${\ displaystyle 3/2}$${\ displaystyle 1.53635}$${\ displaystyle 1.54014}$${\ displaystyle 248/161 \ aproximativ 1.54037}$

Tabel comparativ

Algoritm	Garanție de aproximare	Cea mai proastă listă de cazuri ${\ displaystyle L}$	Complexitatea timpului
Potrivire următoare (NF)	${\ displaystyle NF (L) \ leq 2 \ cdot \ mathrm {OPT} (L) -1}$	${\ displaystyle NF (L) = 2 \ cdot \ mathrm {OPT} (L) -2}$	${\ displaystyle {\ mathcal {O}} (| L |)}$
Prima potrivire (FF)	${\ displaystyle FF (L) \ leq \ lfloor 1.7 \ mathrm {OPT} (L) \ rfloor}$	${\ displaystyle FF (L) = \ lfloor 1.7 \ mathrm {OPT} (L) \ rfloor}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Cel mai potrivit (BF)	${\ displaystyle BF (L) \ leq \ lfloor 1.7 \ mathrm {OPT} (L) \ rfloor}$	${\ displaystyle BF (L) = \ lfloor 1.7 \ mathrm {OPT} (L) \ rfloor}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Cel mai prost (WF)	${\ displaystyle WF (L) \ leq 2 \ cdot \ mathrm {OPT} (L) -1}$	${\ displaystyle WF (L) = 2 \ cdot \ mathrm {OPT} (L) -2}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Aproape cel mai rău potrivit (AWF)	${\ displaystyle R_ {AWF} ^ {\ infty} \ leq 17/10}$	${\ displaystyle R_ {AWF} ^ {\ infty} = 17/10}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Refined-First-Fit (RFF)	${\ displaystyle RFF (L) \ leq (5/3) \ cdot \ mathrm {OPT} (L) +5}$	${\ displaystyle RFF (L) = (5/3) \ mathrm {OPT} (L) +1/3}$(pentru ) ${\ displaystyle \ mathrm {OPT} (L) = 6k + 1}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |))}$
Harmonic-k (Hk)	${\ displaystyle R_ {Hk} ^ {\ infty} \ leq 1.69103}$ pentru ${\ displaystyle k \ rightarrow \ infty}$	${\ displaystyle R_ {Hk} ^ {\ infty} \ geq 1.69103}$	${\ displaystyle {\ mathcal {O}} (| L | \ log (| L |)}$
Armonic rafinat (RH)	${\ displaystyle R_ {RH} ^ {\ infty} \ leq 373/228 \ approx 1.63597}$		${\ displaystyle {\ mathcal {O}} (| L |)}$
Armonic modificat (MH)	${\ displaystyle R_ {MH} ^ {\ infty} \ leq 538/33 \ approx 1.61562}$
Armonic modificat 2 (MH2)	${\ displaystyle R_ {MH2} ^ {\ infty} \ leq 239091/148304 \ approx 1.61217}$
Armonic + 1 (H + 1)		${\ displaystyle R_ {H + 1} ^ {\ infty} \ geq 1.59217}$
Harmonic ++ (H ++)	${\ displaystyle R_ {H ++} ^ {\ infty} \ leq 1.58889}$	${\ displaystyle R_ {H ++} ^ {\ infty} \ geq 1.58333}$

Algoritmi offline

În versiunea offline de ambalare a coșurilor, algoritmul poate vedea toate articolele înainte de a începe să le plaseze în coșuri. Acest lucru permite obținerea unor rapoarte de aproximare îmbunătățite.

Aproximare multiplicativă

Cea mai simplă tehnică utilizată de algoritmi offline este:

• Comandarea listei de intrare prin dimensiune descrescătoare;
• Rulați un algoritm online pe lista comandată.

Johnson a demonstrat că orice algoritm AnyFit A care rulează pe o listă ordonată în funcție de dimensiunea descendentă are un raport de aproximare asimptotic de

${\ displaystyle 1.22 \ approx {\ frac {11} {9}} \ leq R_ {A} ^ {\ infty} \ leq {\ frac {5} {4}} = 1.25}$.

Unii algoritmi din această familie sunt (consultați paginile legate pentru mai multe informații):

• First-fit- descending (FFD) - comandă articolele după dimensiunea descrescătoare, apoi apelează First-Fit. Raportul său de aproximare este, și acest lucru este strâns.${\ displaystyle FFD (I) = 11/9 \ mathrm {OPT} (I) +6/9}$
• Next-Fit- Scending (NFD) - comandă articolele în funcție de dimensiunea descrescătoare, apoi apelează Next-Fit . Raportul său aproximativ este puțin mai mic de 1,7 în cel mai rău caz. De asemenea, a fost analizat probabilistic. Next-Fit împachetează o listă și inversul acesteia în același număr de pubele. Prin urmare, Next-Fit-Increasing are aceleași performanțe ca Next-Fit-Increasing.
• Modificată pentru prima reducere (MFFD) - îmbunătățește FFD pentru articolele mai mari de jumătate de coș clasificând articolele după mărime în patru clase de dimensiuni mari, medii, mici și mici, corespunzătoare articolelor cu dimensiunea> 1/2 coș,> Coșul 1/3,> coșul 1/6 și respectiv articolele mai mici. Garanția sa de aproximare este.${\ displaystyle MFFD (I) \ leq (71/60) \ mathrm {OPT} (I) +1}$

Fernandez de la Vega și Lueker au prezentat un PTAS pentru ambalarea coșurilor. Pentru fiecare , algoritmul lor găsește o soluție cu dimensiunea cel mult și rulează în timp , unde denotă o funcție dependentă doar de . Pentru acest algoritm, au inventat metoda rotunjirii de intrare adaptive : numerele de intrare sunt grupate și rotunjite până la valoarea maximului din fiecare grup. Aceasta produce o instanță cu un număr mic de dimensiuni diferite, care poate fi rezolvată exact prin verificarea tuturor configurațiilor posibile. ${\ displaystyle \ varepsilon> 0}$${\ displaystyle (1+ \ varepsilon) \ mathrm {OPT} +1}$${\ displaystyle {\ mathcal {O}} (n \ log (1 / \ varepsilon)) + {\ mathcal {O}} _ {\ varepsilon} (1)}$${\ displaystyle {\ mathcal {O}} _ {\ varepsilon} (1)}$${\ displaystyle 1 / \ varepsilon}$

Aproximare aditivă

Karmarkar și Karp au prezentat un algoritm cu polinom de execuție în și . Algoritmul lor găsește cel mult o soluție cu dimensiunea . ${\ displaystyle n}$${\ displaystyle 1 / \ varepsilon}$${\ displaystyle \ mathrm {OPT} + {\ mathcal {O}} (\ log ^ {2} (OPT))}$

Rothvoss a prezentat un algoritm care generează cel mult o soluție cu dimensiuni . ${\ displaystyle \ mathrm {OPT} + O (\ log (\ mathrm {OPT}) \ cdot \ log \ log (\ mathrm {OPT}))}$

Hoberg și Rothvoss au îmbunătățit acest algoritm pentru a genera cel mult o soluție cu dimensiuni . Algoritmul este randomizat, iar timpul său de rulare este polinomial în numărul total de itemi. ${\ displaystyle \ mathrm {OPT} + O (\ log (\ mathrm {OPT}))}$

Tabel comparativ

Algoritm	Garanție de aproximare	Cel mai prost caz
Prima reducere (FFD)	${\ displaystyle FFD (I) \ leq 11/9 \ mathrm {OPT} (I) +6/9}$	${\ displaystyle FFD (I) = 11/9 \ mathrm {OPT} (I) +6/9}$
Modified-first-fit-descending (MFFD)	${\ displaystyle MFFD (I) \ leq (71/60) \ mathrm {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)})}$

Algoritmi exacți

Martello și Toth au dezvoltat un algoritm exact pentru problema 1-D de ambalare a coșurilor, numit MTP. O alternativă mai rapidă este algoritmul Bin Completion propus de Korf în 2002 și ulterior îmbunătățit.

O îmbunătățire suplimentară a fost prezentată de Schreiber și Korf în 2013. Noul algoritm îmbunătățit de completare a coșurilor se dovedește a fi cu până la cinci ordine de mărime mai rapid decât Completarea coșurilor pentru probleme non-banale cu 100 de elemente și depășește BCP (ramură și algoritm de reducere și preț) de către Belov și Scheithauer privind problemele care au mai puțin de 20 de coșuri ca soluție optimă. Algoritmul care funcționează cel mai bine depinde de proprietățile problemei, cum ar fi numărul de articole, numărul optim de pubele, spațiul neutilizat în soluția optimă și precizia valorii.

Goemans și Rothvoss a prezentat un algoritm de ambalare bin cu d diferite elemente-dimensiuni, în cazul în care pot exista mai multe elemente cu fiecare dimensiune. Algoritmul lor este polinomial când d este fix și toate numerele sunt date în codare binară.

Ambalarea coșului cu constrângeri de cardinalitate

Există o variantă de împachetare a coșurilor în care există constrângeri de cardinalitate pe coșuri: fiecare coș poate conține cel mult k articole, pentru un număr întreg k fix .

• Krause, Shen și Schwetman introduc această problemă ca o variantă de planificare optimă a lucrărilor : un computer are câteva k procesoare. Există câteva n joburi care durează unitatea (1), dar au cerințe de memorie diferite. Fiecare unitate de timp este considerată un singur coș. Scopul este de a utiliza cât mai puține coșuri (= unități de timp) posibil, asigurându-se în același timp că în fiecare coș, se execută cel mult k joburi. Prezintă mai mulți algoritmi euristici care găsesc o soluție cu cel mult coșuri.${\ displaystyle 2OPT}$
• Kellerer și Pferschy prezintă un algoritm cu run-time , care găsește o soluție cu cel mult coșuri. Algoritmul lor efectuează o căutare binară pentru OPT. Pentru fiecare valoare căutată m , încearcă să împacheteze articolele în 3 m / 2 coșuri.${\ displaystyle O (n ^ {2} \ log {n})}$${\ displaystyle \ lceil {\ frac {3} {2}} \ mathrm {OPT} \ rceil}$

Probleme conexe

În problema ambalării coșurilor, dimensiunea coșurilor este fixă ​​și numărul lor poate fi mărit (dar ar trebui să fie cât mai mic posibil).

În schimb, în problema de partiționare a numărului cu mai multe căi , numărul de coșuri este fix și dimensiunea lor poate fi mărită. Obiectivul este de a găsi o partiție în care dimensiunile coșului să fie cât mai aproape egale este posibil (în varianta numită problemă de planificare multiprocesor sau problemă makepan minimă , obiectivul este specific reducerea dimensiunii celui mai mare coș).

În problema de ambalare a coșului invers , atât numărul de coșuri, cât și dimensiunile acestora sunt fixate, dar dimensiunile articolelor pot fi modificate. Obiectivul este de a atinge perturbarea minimă a vectorului de mărime a articolului, astfel încât toate articolele să poată fi ambalate în numărul prescris de pubele.

În problema maximă de ambalare a coșurilor de resurse , scopul este de a maximiza numărul de coșuri utilizate, astfel încât, pentru o anumită ordonare a coșurilor, niciun articol dintr-un coș ulterior nu se potrivește într-un coș anterior. Într-o problemă dublă, numărul de coșuri este fixat, iar obiectivul este de a reduce la minimum numărul total sau dimensiunea totală a articolelor plasate în coșuri, astfel încât niciun element rămas să nu se potrivească într-un coș neumplut.

În problema acoperirii coșului , dimensiunea coșului este delimitată de jos : obiectivul este de a maximiza numărul de coșuri utilizate astfel încât dimensiunea totală a fiecărui coș să fie cel puțin un prag dat.

În problema corectă a alocării corvoadei indivizibile (o variantă a alocării corecte a articolelor ), articolele reprezintă corvoade și există oameni diferiți, fiecare atribuind o dificultate-valoare diferită fiecărei corvoade. Scopul este de a aloca fiecărei persoane un set de treburi cu o limită superioară pe valoarea sa totală de dificultate (astfel, fiecare persoană corespunde unui coș). Multe tehnici de ambalare a coșurilor sunt folosite și în această problemă.

În problema tăierii ghilotinei , atât articolele, cât și „coșurile” sunt mai degrabă dreptunghiuri bidimensionale decât numere unidimensionale, iar articolele trebuie tăiate din coș folosind tăieturi cap la cap.

În problema egoistei de ambalare a coșurilor , fiecare articol este un jucător care dorește să-și minimizeze costul.

Există, de asemenea, o variantă de ambalare a coșurilor în care costul care ar trebui minimizat nu este numărul de coșuri, ci mai degrabă o anumită funcție concavă a numărului de articole din fiecare coș.

Alte variante sunt ambalarea bidimensională , ambalarea bidimensională , ambalarea bidonului cu livrare ,

Implementări

• Online : vizualizarea euristicii pentru ambalarea coșurilor 1D și 2D
• Python: pachetul binpacking conține algoritmi lacome pentru rezolvarea a două probleme de ambalare bin tipice: (i) elementele de ambalaj într - un număr constant de pubele, (ii) elementele de ambalaj într - un număr redus de pubele de mărime constantă.
• C ++ : pachetul de ambalare bin conține diferiți algoritmi lacomi, precum și date de testare.
• Pachetul OR-tools conține algoritmi de împachetare bin în C ++, cu împachetări în Python, C # și Java.
• C : Implementarea a 7 algoritmi clasici aproximativi de împachetare a coșurilor în C cu rezultate și imagini
• PHP : Clasa PHP pentru a împacheta fișiere fără a depăși o anumită limită de dimensiune
• Haskell : Implementarea mai multor euristici de ambalare a coșurilor , inclusiv FFD și MFFD.
• C : Fpart: instrument de linie de comandă open-source pentru a împacheta fișiere (C, licențiat BSD)
• C # : Solver de ambalare și tăiere a coșurilor
• Java : caparf - Cadru de cercetare pentru algoritmi de tăiere și ambalare , incluzând un număr de algoritmi de ambalare a coșurilor și date de testare.

Referințe