Container problem

The container problem or bin packing problem is a combinatorial optimization problem based on the following question:

• Given: A number of "containers" ( English bin ) the size and a number of "objects" with the weights (sizes) . ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b}$
• Question: Can the "objects" be distributed to the "containers" ( packing ) in such a way that none of the "containers" overflow? Formally: ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle \exists \ f\colon \{1,\dotsc ,n\}\to \{1,\dotsc ,k\}{\text{, so dass für alle }}j\in \{1,\dotsc ,k\}\quad \sum _{f(i)=j}a_{i}\leq b{\text{ gilt?}}}$

The decision problem described above is NP-complete ; the associated optimization problem - finding an assignment in which the number of containers is minimized - is NP-difficult .

The formulation of the bin packing problem given here is only the motivation or basis for a large number of other packing problems that play a major role in the packaging industry , among others .

A somewhat more general formal definition describes the bin packing problem as the determination of a partition and assignment of a set of objects so that a certain condition is fulfilled or an objective function is minimized or maximized.

A distinction is made between offline and online variants, whereby offline means that all objects are known in advance. In the online process, a decision must be made immediately as to which container the object will be packed in.

Algorithms

Since bin packing is an NP-hard problem, it is probably impossible to solve in polynomial running time. Johnson's approximation algorithm First Fit Decreasing solves the problem in polynomial time with a sharp asymptotic quality guarantee of (the quality guarantee is not asymptotic ). ${\displaystyle 11 \over 9}$ ${\displaystyle 3 \over 2}$

Sortiere die Objekte nach absteigendem Gewicht
Füge die Objekte der Reihe nach ein,
sodass jedes in den ersten Behälter gegeben wird, in dem noch genug Platz ist.
Falls in keinem der bereits geöffneten Behälter genügend Platz ist, öffne einen neuen.

The runtime is (both for sorting and inserting). The same results apply to Best Fit Decreasing . An object is not inserted into the first container in which it fits, but into the container in which it just fits (the remaining capacity is thus minimized). ${\displaystyle {\mathcal {O}}(n\cdot \log n)}$

With the online version it is not possible to sort the objects in advance by weight. The First Fit and Best Fit algorithms work in the same way as those mentioned above, but without prior sorting. Both algorithms have a sharp asymptotic quality guarantee of 1.7 and a running time of . Best Fit searches for the smallest free space that still fits in all the containers available so far. ${\displaystyle {\mathcal {O}}(n\cdot \log n)}$

The naive Next Fit algorithm packs the objects one after the other into the last opened container, if they fit. Otherwise the container is closed, a new one is opened and the current object is placed in the empty container. The asymptotic quality guarantee is 2, the term . The advantage of this naive algorithm is that only one container is open at a time (which can be a condition in practical use). ${\displaystyle {\mathcal {O}}(n)}$

literature

• Bernhard Korte, Jens Vygen: Combinatorial Optimization. Springer, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7 , p. 485ff

Web links

• Optimizing Three-Dimensional Bin Packing
• Article in the algorithm of the week