Das Behälterproblem

Beim Umzug füllen Sie einen Karton nach dem anderen und fragen sich, ob eine klügere Reihenfolge weniger gebraucht hätte. Das ist das Behälterproblem, und es ist berüchtigt schwer: Selbst Computer finden die wenigsten Behälter bei großen Eingaben nur durch geschickte Suche. Einfache Regeln kommen aber erstaunlich nahe heran.

Gleich hohe Behälter, gefüllt mit gestapelten farbigen Gegenständen verschiedener Größe, darüber warten weitere Gegenstände
Gleich hohe Behälter, gefüllt mit gestapelten farbigen Gegenständen verschiedener Größe, darüber warten weitere Gegenstände

Das Problem

Gegeben sind Gegenstände mit Größen und Behälter, die alle gleich viel fassen. Jeder Gegenstand soll so in einen Behälter, dass kein Behälter überläuft, und dabei sollen möglichst wenige Behälter benutzt werden. Die Größen können für Gewichte, Längen, Zeitdauern oder Dateigrößen stehen. Das klingt nach einem Rätsel für einen verregneten Nachmittag, ist aber NP-schwer: Es ist kein Verfahren bekannt, das für jede Eingabe schnell die wenigsten Behälter findet.

Schnelle Regeln

Next Fit füllt einen Behälter, bis der nächste Gegenstand nicht mehr passt, beginnt dann einen neuen Behälter und blickt nie zurück. First Fit hält alle Behälter offen und legt jeden Gegenstand in den ersten Behälter mit genug Platz. Best Fit legt jeden Gegenstand in den vollsten Behälter, der noch Platz hat. Alle drei entscheiden sofort; das ist nützlich, wenn die Gegenstände einzeln ankommen und gleich platziert werden müssen.

Erst sortieren

Große Gegenstände sind die schwierigen, weil sie viel freien Platz brauchen. Sortiert man die Gegenstände vom größten zum kleinsten und verwendet dann First Fit oder Best Fit, kommen die großen hinein, solange die Behälter noch leer sind, und die kleinen füllen die Lücken. First Fit Decreasing braucht nie mehr als 11/9 der wenigsten Behälter plus eine Konstante, gegenüber dem 1,7-Fachen bei First Fit mit unsortierten Gegenständen.

Ein Beispiel

Nehmen Sie Behälter der Größe 10 und die Gegenstände 2, 3, 2, 1, 3, 4, 5, 6, 7 und 7, zusammen 40. First Fit legt 2, 3, 2 und 1 in den ersten Behälter und 3 und 4 in den zweiten, danach brauchen 5, 6, 7 und 7 jeweils einen eigenen Behälter: 6 Behälter. Vom größten an sortiert, ergibt First Fit Decreasing 7 + 3, 7 + 3, 6 + 4 und 5 + 2 + 2 + 1: 4 volle Behälter, genau die untere Schranke von 40 / 10 = 4.

Die wenigsten Behälter finden

Bei wenigen Gegenständen lässt sich die exakte Lösung durch dynamische Programmierung über Teilmengen finden: für jede Menge von Gegenständen die wenigsten Behälter und den leersten letzten Behälter, die sie aufnehmen, aufgebaut aus den Mengen mit einem Gegenstand weniger. Das dauert etwa 2ⁿ·n Schritte bei n Gegenständen. Größere Instanzen löst man mit Branch and Bound oder ganzzahliger linearer Optimierung, und die untere Schranke zeigt, wie weit eine Packung höchstens vom Optimum entfernt ist.

Wo es vorkommt

Lkw und Container beladen, Rohre oder Papierrollen mit möglichst wenig Verschnitt aus Standardlängen schneiden (das Zuschnittproblem), virtuelle Maschinen auf Server verteilen und Dateien auf Datenträger packen: Das alles sind Behälterprobleme. In zwei und drei Dimensionen, mit Kisten statt Zahlen, ist das Problem noch schwerer.

Häufig gestellte Fragen

Was ist der Unterschied zwischen Online- und Offline-Bin-Packing?

Online muss jeder Gegenstand platziert werden, sobald er ankommt, ohne die übrigen zu kennen; so arbeiten Next Fit, First Fit und Best Fit. Offline sind alle Gegenstände im Voraus bekannt, sodass man sie zuerst sortieren kann, wie es First Fit Decreasing tut.

Wie nah kommt First Fit Decreasing an das Optimum heran?

Es braucht höchstens 11/9 der wenigsten Behälter plus 6/9 eines Behälters, eine Schranke, von der György Dósa 2007 bewiesen hat, dass sie scharf ist. Bei typischen Eingaben ist das Ergebnis meist optimal oder nur einen Behälter davon entfernt.

Ist das Behälterproblem dasselbe wie das Rucksackproblem?

Sie sind verwandt, aber verschieden. Beim Rucksackproblem füllt man einen Rucksack mit den wertvollsten Gegenständen; beim Behälterproblem kommt jeder Gegenstand in möglichst wenige Rucksäcke. Exakte Löser für das Behälterproblem lösen oft immer wieder rucksackähnliche Probleme.

Warum erlaubt die App nur 12 Gegenstände?

Weil die exakte Lösung jede Menge von Gegenständen betrachtet, und 12 Gegenstände ergeben schon 4.096 Mengen. Die schnellen Regeln kämen mit Tausenden von Gegenständen zurecht, die Zeichnung und der Vergleich mit der exakten Lösung aber nicht.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Behälterproblem ausprobieren