Behälterproblem

Das Behälterproblem oder auch bin packing problem ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert:

• Gegeben: Eine Anzahl ${\displaystyle k\in \mathbb {N} }$ von „Behältern“ (englisch bin) der Größe ${\displaystyle b\in \mathbb {N} }$ und eine Anzahl ${\displaystyle n\in \mathbb {N} }$ „Objekte“ mit den Größen ${\displaystyle a_{1},a_{2},\dotsc ,a_{n}\ \leq \ b}$.
• Frage: Können die ${\displaystyle n}$ „Objekte“ so auf die ${\displaystyle k}$ „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft? Formal:

${\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?}}}$

Das oben beschriebene Entscheidungsproblem ist NP-vollständig; das zugehörige Optimierungsproblem – das Finden einer Zuordnung, bei der die Anzahl an Behältern minimiert wird – ist NP-schwer.

Die hier gegebene Formulierung des Bin-Packing-Problems ist nur die Motivation beziehungsweise Basis für eine Vielzahl weiterer Packing-Problems, die unter anderem in der Verpackungsindustrie eine große Rolle spielen.

Eine etwas allgemeiner formale Definition beschreibt das Bin-Packing-Problem als die Bestimmung einer Partition und Zuordnung einer Menge von Objekten, so dass eine bestimmte Bedingung erfüllt bzw. eine Zielfunktion minimiert oder maximiert wird.

Man unterscheidet zwischen Offline- und Online-Varianten, wobei offline bedeutet, dass im Voraus alle Objekte bekannt sind. Bei Online-Verfahren muss sofort entschieden werden, in welchen Behälter das Objekt gepackt wird, ohne die folgenden Objekte zu kennen.