Behälterproblem

Das Behälterproblem oder auch bin packing problem 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 Gewichten (Größen) . * Frage: Können die „Objekte“ so auf die „Behälter“ verteilt (packing) werden, dass keiner der „Behälter“ überläuft? Formal: 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.