Bin packing problem


Bin packing problem

In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. In it, objects of different volumes must be packed into a finite number of bins of capacity "V" in a way that minimizes the number of bins used.

There are many variations of this problem, such as 2D packing, linear packing, packing by weight, packing by cost, and so on. They have many applications, such as filling up containers, loading trucks with weight capacity, and creating file backup in removable media.

Since it is NP-hard, the most efficient known algorithms use heuristics to accomplish results which, though very good in most cases, may not be the optimal solution. For example, the first fit algorithm provides a fast but often nonoptimal solution, involving placing each item into the first bin in which it will fit. It requires Θ("n" log "n") time. The algorithm can be made much more effective by first sorting the list of elements into decreasing order (sometimes known as the first-fit decreasing algorithm), although this does not guarantee an optimal solution, and for longer lists may increase the running time of the algorithm.

Formal statement

Given a bin size V and a list a_1,dots,a_n of sizes of the items to pack, find an integer B and a B-partition S_1 cup dots cup S_B of {1,dots,n} such that sum_{i in S_k} a_i leq V for all k=1,dots,B.

A solution is "optimal" if it has minimal B. The B-value for an optimal solution is denoted OPT below.

Analysis of heuristic algorithms

The "best fit decreasing" and "first fit decreasing" strategies are among the simplest heuristic algorithms for solving the bin packing problem. They have been shown to use no more than 11/9 OPT + 1 bins (where OPT is the number of bins given by the optimal solution). [M. Yue, "A simple proof of the inequality FFD(L) ≤ (11/9)OPT(L) + 1, for all L, for the FFD bin-packing algorithm", "Acta Mathematicae Applicatae Sinica" 7 (1991), pp. 321–331.] The simpler of these, the "First Fit Decreasing" strategy, operates by first sorting the items to be inserted in decreasing order by volume, and then inserting each item into the first bin in the list with sufficient remaining space. The sorting step is relatively expensive, but without it we only achieve the looser bound of 17/10 OPT + 2. Recently, it was proved that the bound 11/9 OPT + 6/9 for FFD is tight. [György Dósa, "The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I)≤(11/9)OPT(I)+6/9", ESCAPE 2007, "Springer LNCS" "4614" (2007), pp. 1–11.] MFDD [Michael R. Garey and David S. Johnson, "A 71/60 theorem for bin packing", "Journal of Complexity", Vol. 1 (1985), pp. 65–106.] (a variant of FFD) uses no more than 71/60 OPT + 1 bins [Yue Minyi and Zhang Lei, "A simple proof of the inequality MFFD(L) ≤ 71/60 OPT(L) + 1, L for the MFFD bin-packing algorithm", "Acta Mathematicae Applicatae Sinica" 11 (1995), pp. 318–330.] (i.e. bounded by about 1.18×opt, compared to about 1.22×opt for FFD).

Although these simple strategies are often good enough, efficient approximation algorithms have been demonstrated [Vijay V. Vazirani, Approximation Algorithms. Springer. ISBN 3-540-65367-8. p. 74.] that can solve the bin packing problem within "any" fixed percentage of the optimal solution for sufficiently large inputs (this is called an asymptotic polynomial-time approximation scheme). This is an advantage the problem has over many other common NP-hard problems, some of which cannot be approximated within any constant factor at all.

See also

* Knapsack problem
* Packing problem
* Partition problem
* Multiprocessor scheduling problem
* Subset sum problem

References

* Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A4.1: SR1, p. 226.
* David S. Johnson, Alan J. Demers, Jeffrey D. Ullman, M. R. Garey, Ronald L. Graham. [http://siamdl.aip.org/dbt/dbt.jsp?KEY=SMJCAT&Volume=3&Issue=4 Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms] . SICOMP, Volume 3, Issue 4. 1974.
* Lodi A., Martello S., Vigo, D. (2002) Recent advances on two-dimensional bin packing problems. Discrete Appl. Math., Volume 123, p. 379-396

External links

* [http://www.phpclasses.org/browse/package/2027.html PHP Class to pack files without exceeding a given size limit] on the PHPClasses Repository
* [http://portal.acm.org/citation.cfm?id=3833&jmp=abstract&dl=portal&dl=ACM]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Bin-Packing-Problem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin Packing Problem — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin packing problem — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Packing problem — Part of a series on Puzzles …   Wikipedia

  • BIN PACKING — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-Packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Bin-packing — Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert: Gegeben: Eine Anzahl von „Behältern“ (englisch bin) der Größe und eine Anzahl „Objekte“ mit den Größen …   Deutsch Wikipedia

  • Probleme de bin packing — Problème de bin packing Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème… …   Wikipédia en Français

  • Problème de bin packing — Le problème de bin packing relève de la recherche opérationnelle et de l optimisation combinatoire. Il s agit de trouver le rangement le plus économique possible pour un ensemble d articles dans des boîtes. Le problème classique se définit en une …   Wikipédia en Français

  • Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… …   Wikipedia