{"id":4770,"date":"2021-08-11T04:21:26","date_gmt":"2021-08-11T04:21:26","guid":{"rendered":"https:\/\/lamarr-institute.org\/blog\/bin-packing\/"},"modified":"2025-11-12T14:54:48","modified_gmt":"2025-11-12T14:54:48","slug":"bin-packing","status":"publish","type":"blog","link":"https:\/\/lamarr-institute.org\/de\/blog\/bin-packing\/","title":{"rendered":"Bin-Packing: Wenn auch Computer nur geschickt sch\u00e4tzen k\u00f6nnen"},"content":{"rendered":"\n

Das Bin-Packing-Problem<\/strong> („Beh\u00e4lterproblem“) geh\u00f6rt zu den schwersten Problemen f\u00fcr Digitalrechner, die der Informatik bekannt sind. Es geht um die Fragestellung:<\/p>\n\n\n\n

Gegeben sei eine Menge von Objekten bestimmter Gr\u00f6\u00dfe und eine Menge von Containern mit einem bestimmten Fassungsverm\u00f6gen. Gibt es eine M\u00f6glichkeit alle Objekte in den gegebenen Containern zu verstauen?<\/p>\n\n\n\n

Auch wenn der Name und das hier verwendete Beispiel vor allem Anwendungen in der Logistik nahelegen, lassen sich durch Bin-Packing unter anderem auch Probleme der Routenplanung oder Ablaufsteuerung\/Koordinierung ausdr\u00fccken. In diesem Beitrag betrachten wir zwei naive L\u00f6sungsstrategien f\u00fcr ein konkretes Beispiel des Bin-Packing und vergleichen, unter welchen Optimalit\u00e4tskriterien die eine L\u00f6sung der anderen vorzuziehen ist.<\/p>\n\n\n\n

Bin-Packing<\/span><\/h2>\n\n\n\n

Bin-Packing ist ein kombinatorisches Optimierungsproblem<\/strong>. Ganz allgemein zeichnet diese Probleme aus, dass sie nach einer ganz bestimmten Kombination problemspezifischer Entit\u00e4ten suchen, sodass diese eine Wunscheigenschaft erf\u00fcllen: Beim Bin-Packing ist dies die Anordnung verschiedener Objekte mit bekannten Eigenschaften, sodass diese in die gegebene Menge an Containern passen.<\/p>\n\n\n\n

In der Praxis ist man hierbei nicht nur an einer Ja-Nein-Antwort, also ob<\/em> alle Objekte in die gegebenen Container passen, interessiert. Vielmehr ist von Interesse wie<\/em>, das hei\u00dft in welcher konkreten Konfiguration<\/strong>, die Gegenst\u00e4nde in den Beh\u00e4ltern anzuordnen sind. Aus \u00f6konomischer Sicht ist es nachvollziehbar dabei nicht nur nach einer L\u00f6sung zu suchen, die die Objekte auf beliebige Art und Weise verstaut, sondern am besten auch so, dass so wenige Beh\u00e4lter wie m\u00f6glich verbraucht werden. Genauso gut k\u00f6nnte aber auch die zur Verf\u00fcgung stehende Zeit zum Verpacken begrenzt sein, sodass man einen Kompromiss zwischen Packdichte und Rechenzeit in Kauf nimmt.<\/p>\n\n\n\n

Die gro\u00dfe Schwierigkeit bei kombinatorischen Optimierungsproblemen besteht darin, dass im Vorhinein unbekannt ist, ob eine Konfiguration mit der gew\u00fcnschten Eigenschaft \u00fcberhaupt existiert. Genau so wenig wei\u00df man, was die n\u00e4chstbeste erreichbare L\u00f6sung ist. Um wirklich die optimale<\/em> erreichbare Konfiguration zu finden, m\u00fcssen daher alle m\u00f6glichen Konfigurationen berechnet und verglichen werden. Die Menge der zu vergleichenden Kombinationen w\u00e4chst dabei mit der Menge der zu kombinierenden Objekte exponentiell (oder st\u00e4rker) an, sodass es unm\u00f6glich ist die n\u00f6tigen Berechnungen f\u00fcr eine garantiert optimale L\u00f6sung auf Digitalrechnern durchzuf\u00fchren. Daher nutzt man in der Praxis sogenannte Heuristiken<\/strong>. Diese versuchen durch geschickte Annahmen den Suchraum<\/strong>, also die Menge aller in Betracht zu ziehenden Konfigurationen, so einzugrenzen, dass sich m\u00f6glichst viele gute und m\u00f6glichst wenig schlechte Konfigurationen darin befinden.<\/p>\n\n\n\n

Bin-Packing in 2D<\/span><\/h2>\n\n\n\n

Wir schauen uns in diesem Beitrag eine zweidimensionale Variante des Bin-Packing-Problems an, in der wir rechteckige Objekte in einen quadratischen 10×10 Container packen m\u00f6chten. Es gelten dabei folgende Regeln: Die Objekte d\u00fcrfen um 90 Grad gedreht werden. Ist ein Objekt einmal platziert, k\u00f6nnen wir seine Position nicht mehr \u00e4ndern. Eine Konfiguration ist g\u00fcltig, wenn sich die Objekte nicht \u00fcberdecken oder \u00fcber den Containerrand hinausragen.<\/p>\n\n\n\n

Abbildung 1 zeigt den in diesem Beitrag behandelten Anwendungsfall:<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Gepackte Container: Optimale Konfigurationen erm\u00f6glichen hier eine dichte Platzierung aller Objekte.<\/figcaption><\/figure>\n\n\n\n

Die Abbildung zeigt zwei Container, die mit farbigen Objekten l\u00fcckenlos (dicht) gepackt sind. Diese Konfiguration stellt eine optimale L\u00f6sung dar. Es l\u00e4sst sich leicht erkennen, dass es mehrere dichte Konfigurationen, also mehrere optimale L\u00f6sungen gibt. Als Referenz: Das kleinste Objekt ist 1×1 Einheiten gro\u00df und das gr\u00f6\u00dfte 6×5 Einheiten breit und hoch:<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Objekte, die in zuf\u00e4lliger Reihenfolge aus den Containern geholt wurden.<\/figcaption><\/figure>\n\n\n\n

Eine Entnahme der Objekte in zuf\u00e4lliger Reihenfolge und Rotation aus dem Container bildet nun den Ausgangspunkt f\u00fcr unser Anwendungsbeispiel.<\/p>\n\n\n\n

Max-Rest und First-Fit Algorithmen<\/h2>\n\n\n\n

Anhand welcher Heuristiken k\u00f6nnen nun Konfigurationen erzeugt werden, die sich einer optimalen Konfiguration ann\u00e4hern? Wie bereits dargelegt, wollen wir versuchen die Container m\u00f6glichst dicht zu bepacken. Zum anderen wollen wir auch den Zeitfaktor ber\u00fccksichtigen.<\/p>\n\n\n\n

Max-Rest-Algorithmus<\/strong><\/em>. Fangen wir mit der \u00dcberlegung zu einer zeitkritischen Anwendung an: Wenn in einem Container noch viel Platz ist, ist die Wahrscheinlichkeit hoch, dort ein Objekt platzieren zu k\u00f6nnen. Wir legen damit den Fokus darauf, m\u00f6glichst selten ein Objekt in einem Container platzieren zu wollen, in dem eigentlich kein Platz mehr ist. So sparen wir Zeit. \u00dcber diese Motivation gelangen wir zum Max-Rest-Algorithmus. Dieser geht beim platzieren eines Objekts wie folgt vor:<\/p>\n\n\n\n

W\u00e4hle den Container aus, der noch am meisten freien Platz<\/em> zur Verf\u00fcgung hat. Versuche das Objekt darin zu platzieren. Ist dies nicht m\u00f6glich, nimm einen neuen Container und platziere das Objekt darin.<\/p>\n\n\n\n

First-Fit Algorithmus<\/strong><\/em>. Wenn es nun wichtiger ist, einen Container m\u00f6glichst dicht zu packen und daf\u00fcr eine gr\u00f6\u00dfere Anzahl von Rechenschritten zu investieren, k\u00f6nnten wir folgende \u00dcberlegung anstellen: Je \u00f6fter wir versuchen Platz f\u00fcr ein weiteres Objekt in einem bestimmten Container zu finden, desto h\u00f6her ist die Wahrscheinlichkeit diesen dicht zu bepacken. Dieser Gedanke f\u00fchrt zum First-Fit Algorithmus. Bei diesem ist nun wichtig, dass die Container eine feste Reihenfolge<\/strong> haben. Der Algorithmus platziert die Objekte nach folgender Logik:<\/p>\n\n\n\n

Gehe die Liste von Containern von vorne nach hinten durch. Platziere das Objekt in den ersten Container, in den es passt<\/em>. Passt es in keinen Container der Liste, nimm einen neuen Container, platziere das Objekt darin und f\u00fcge den Container hinten<\/em> an die Liste der Container an.<\/p>\n\n\n\n

Platzieren eines Objekts<\/strong><\/em>. Um die Ausgaben der Algorithmen nachvollziehen zu k\u00f6nnen, m\u00fcssen wir noch festlegen wie genau ein Objekt in einen gegebenen Container platziert wird. Wir suchen in dem Container dabei wie folgt nach einem freien Platz:<\/p>\n\n\n\n

Berechne alle freien Positionen in der Box. Ist die Fl\u00e4che des zu platzierenden Objektes gr\u00f6\u00dfer als die im Container insgesamt noch verf\u00fcgbare Fl\u00e4che, melde einen Fehler und brich ab. Gibt es noch genug freie Positionen, so gehe diese alle so durch, dass du die Position w\u00e4hlst, die am weitesten links und so weit wie m\u00f6glich unten ist. Platziere die linke untere Ecke des Objekts auf dieser Position, wenn es sich dort nicht mit anderen Objekten \u00fcberdeckt; falls es zu einer \u00dcberdeckung kommt, drehe das Objekt um 90 Grad im Uhrzeigersinn und \u00fcberpr\u00fcfe noch einmal auf \u00dcberdeckung. Kann das Objekt so auch nicht platziert werden, gehe zum n\u00e4chsten freien Punkt. Hast du bereits jeden freien Punkt in dem Container probiert, melde einen Fehler.<\/p>\n\n\n\n

Online Szenario<\/h2>\n\n\n\n

Wir pr\u00e4sentieren den verwendeten Algorithmen die Objekte zun\u00e4chst in genau der Reihenfolge, in der wir sie oben zuf\u00e4llig aus den Containern geholt haben. Damit simulieren wir ein online Szenario<\/em>, in welchem wir kein Vorwissen dar\u00fcber haben, wie viele Objekte zu verstauen sind oder welche Eigenschaften (Gr\u00f6\u00dfe) diese haben. Schauen wir nun, welche Konfigurationen wir mit Max-Rest und First-Fit finden. Das Ergebnis des Max-Rest Algorithmus sehen wir in folgender Abbildung:<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Max-Rest-Algorithmus<\/figcaption><\/figure>\n\n\n\n

Max-Rest schafft es, alle Objekte in 3 Containern unterzubringen. Es f\u00e4llt auf, dass es in jedem Container noch gro\u00dfe, zusammenh\u00e4ngende freie Fl\u00e4chen gibt (schwarze Punkte). In den Containern sind je [27, 25, 48] Einheiten frei. Der Algorithmus hat nur 2-mal versucht ein Objekt in einem Container zu platzieren, in den es nicht mehr hineinpasste (Fehlversuch).<\/p>\n\n\n\n

Die Ausgabe des First-Fit Algorithmus sieht deutlich anders aus:<\/p>\n\n\n\n

\"-
\u00a9 ML2R
First-Fit Algorithmus<\/figcaption><\/figure>\n\n\n\n

In jedem Container gibt es noch freie Punkte, aber die ersten beiden Container sind zu \u00fcber 90% gef\u00fcllt. Daf\u00fcr ist im Letzten nur ein einziges Objekt verstaut. Unter diesem Gesichtspunkt sind die Ergebnisse von First-Fit besser zu bewerten als die von Max-Rest. First-Fit passierten jedoch deutlich mehr, n\u00e4mlich 11, Fehlversuche beim Platzieren der Objekte. Beide Beobachtungen sind zu erwarten. First-Fit schaut immer zuerst in den vorderen Containern nach, ob ein Objekt hineinpasst. Diese f\u00fcllen sich \u00fcber die Zeit. In der Folge k\u00f6nnen gr\u00f6\u00dfere Objekte nicht mehr erfolgreich platziert werden, f\u00fcr die kleinsten Objekte hingegen wird der letzte freie Platz genutzt.<\/p>\n\n\n\n

Offline Szenario<\/h2>\n\n\n\n

Wir haben eben unter der Annahme gearbeitet, nicht zu wissen, welche oder wie viele Objekte zu verstauen sind. Schauen wir uns zum Abschluss nun noch den offline<\/strong> Fall an. In diesem gehen wir davon aus, dass wir die Menge der Objekte im Vorhinein kennen und diese vorverarbeiten d\u00fcrfen. Eine sehr einfache Vorverarbeitung w\u00e4re eine Sortierung der Objekte, zum Beispiel absteigend nach Gr\u00f6\u00dfe. Sortieren wir die Objekte nach Fl\u00e4cheninhalt und Breite, erhalten wir folgende Reihenfolge:<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Die zu verpackenden Objekte sortiert nach Fl\u00e4che und Breite<\/figcaption><\/figure>\n\n\n\n

Wenden wir nun wieder die beiden Heuristiken an. Abbildungen 6 und 7 zeigen jeweils das Ergebnis des Max-Rest und des First-Fit Algorithmus auf der sortierten Liste. Letzterer wird bei Anwendung auf eine sortierte Liste auch als First-Fit-Decreasing<\/strong> Algorithmus bezeichnet.<\/p>\n\n\n\n

\"-
\u00a9 ML2R
Ergebnis von Max-Rest auf sortierter Liste<\/figcaption><\/figure>\n\n\n\n
\"-
\u00a9 ML2R
Ergebnis von First-Fit auf sortierter Liste (First-Fit-Decreasing) <\/figcaption><\/figure>\n\n\n\n

Beide Algorithmen liefern erneut je drei Container zur\u00fcck. Bei Max-Rest sind in den Containern noch je [18, 16, 66] Positionen frei. Die Auslastung der ersten beiden hat sich also erh\u00f6ht und im Letzten ist mehr Platz frei geworden. Dabei hat der Algorithmus erneut nur 2 Fehlversuche bei der Platzierung durchlaufen.<\/p>\n\n\n\n

Der erste Container von First-Fit-Decreasing sieht dem von Max-Rest sehr \u00e4hnlich. First-Fit-Decreasing hat es allerdings geschafft, die l\u00e4nglichen L\u00fccken restlos aufzuf\u00fcllen und den Container dicht zu packen. Die verbleibende Kapazit\u00e4t der Container betr\u00e4gt je [0, 12, 88]. Die Auslastung des zweiten Containers hat sich folglich leicht erh\u00f6ht, die des letzten leicht verringert. Die Anzahl der Fehlversuche der Platzierung betr\u00e4gt 22, das entspricht einer Verdoppelung. Auch das ist mit einem Blick auf den ersten Container erkl\u00e4rbar. Dieser war mit den gr\u00f6\u00dften drei Objekten bereits so sehr bef\u00fcllt, dass nur die kleinsten Objekte noch Platz darin fanden. Diese wurden aber erst ganz zum Schluss einsortiert, der Algorithmus hat also f\u00fcr alle Objekte mittlerer Gr\u00f6\u00dfe erfolglos versucht diese in den ersten Container zu packen.<\/p>\n\n\n\n

In der Tabelle fassen wir noch einmal die gesammelten Statistiken zusammen:<\/p>\n\n\n\n

Algorithmus<\/strong><\/td>Freie Kapazit\u00e4t pro Container<\/strong><\/td>Anzahl Fehlversuche bei Platzierung<\/strong><\/td><\/tr>
Max-Rest<\/td>[27, 25, 48]<\/td>2<\/td><\/tr>
First-Fit<\/td>[3, 6, 91]<\/td>11<\/td><\/tr>
Max-Rest sortiert<\/td>[18, 16, 66]<\/td>2<\/td><\/tr>
First-Fit sortiert<\/td>[0, 12, 88]<\/td>22<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Die Objekte vorzuverarbeiten hat bei beiden Algorithmen geholfen die Container dichter zu packen. Dabei hat es First-Fit geschafft einen Container l\u00fcckenlos zu f\u00fcllen. Ist Zeit ein begrenzender Faktor, empfiehlt sich gem\u00e4\u00df dieser Analyse eher der Max-Rest Algorithmus, weil es bei diesem zu deutlich weniger Fehlversuchen gekommen ist.<\/p>\n\n\n\n

Durch geschicktes Raten gut kombinieren<\/h2>\n\n\n\n

In diesem Beitrag haben wir gelernt, dass kombinatorische Optimierungsprobleme auch in Zukunft un\u00fcberwindare H\u00fcrden f\u00fcr unsere Digitalrechner darstellen werden. Die beste Handlungsempfehlung ist in diesem Fall geschickt zu raten. Dabei erhalten wir zwar nicht unbedingt die optimale L\u00f6sung, aber solche Ans\u00e4tze k\u00f6nnen durchaus akzeptable Ergebnisse liefern. Konkret haben wir das Bin-Packing genauer betrachtet und die zwei naiven L\u00f6sungsstrategien Max-Rest und First-Fit in einem online und einem offline Szenario verglichen. Weitere naive Strategien w\u00e4ren der Next-Fit und der Best-Fit Algorithmus. Auch evolution\u00e4re Algorithmen liefern gute Heuristiken und finden praktische Anwendung. Eine solche Anwendung findet sich in dem Blogbeitrag „Evolution\u00e4re Optimierung von Quantenschaltkreisen<\/a>„, der sich mit jener Hardware besch\u00e4ftigt, die kombinatorische Optimierung potenziell traktabler machen k\u00f6nnte.<\/p>\n\n\n\n

ML2R Autumn School 2021<\/h2>\n\n\n\n

Kombinatorische Optimierung ist kein \u00fcbliches Anwendungsgebiet f\u00fcr Verfahren des Maschinellen Lernens. Auf der diesj\u00e4hrigen ML2R Autumn School<\/a> bieten wir vom 04.-08. Oktober einen Rahmen f\u00fcr motivierte Masterandinnen und Doktorand<\/em>innen, um kreativ \u00fcber M\u00f6glichkeiten nachzudenken, Verfahren des Maschinellen Lernens auf kombinatorische Strukturen anzuwenden. Der Fokus wird auf einer wohldefinierten Version des Bin-Packing-Problems liegen, an dem in Kleingruppen praktisch gearbeitet wird. Die Teilnahme an der Autumn School ist kostenlos, die Anzahl der Pl\u00e4tze jedoch begrenzt. Bewerbungsschluss ist der 29. August.<\/p>\n","protected":false},"excerpt":{"rendered":"

Bin-Packing geh\u00f6rt zu der viel untersuchten Klasse der kombinatorischen Optimierungsprobleme. In diesem Beitrag verwenden und vergleichen wir zwei praktikable L\u00f6sungsstrategien f\u00fcr ein konkretes Beispiel.<\/p>\n","protected":false},"author":2,"featured_media":3664,"template":"","meta":{"_acf_changed":false,"footnotes":""},"blog-category":[1416,396],"blog-tag":[1519,1552,1560],"class_list":["post-4770","blog","type-blog","status-publish","has-post-thumbnail","hentry","blog-category-alle-blogbeitraege","blog-category-forschung","blog-tag-industrie-4-0","blog-tag-logistik","blog-tag-optimierung"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4770","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/blog"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/2"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4770\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media\/3664"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=4770"}],"wp:term":[{"taxonomy":"blog-category","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-category?post=4770"},{"taxonomy":"blog-tag","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-tag?post=4770"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}