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) .
- Question: Can the "objects" be distributed to the "containers" ( packing ) in such a way that none of the "containers" overflow? Formally:
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 ).
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).
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.
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).
literature
- Bernhard Korte, Jens Vygen: Combinatorial Optimization. Springer, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7 , p. 485ff