Bin-Packing

Das Behälterproblem oder auch Bin Packing ist ein kombinatorisches Optimierungsproblem, das auf folgender Fragestellung basiert:

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

Formal:

$\exists\ f : \{1,..,n\} \to \{1,..,k\}\ \mbox{, so dass }\forall\ j := 1,..,k \quad \sum_{f(i)=j} a_i \leq b \mbox{ 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.

Siehe auch

• Rucksackproblem
• Operations Research
• Komplexitätsklasse

Weblinks

• Artikel im Algorithmus der Woche