Zuschnittsoptimierung

Guntram Scheithauer ist Mathematiker und forscht an der TU Dresden. Seit seiner Promotion gilt sein Interesse der diskreten Mathematik und der Optimierung. Sein Einstieg in dieses Teilgebiet der Mathematik waren Rundreiseprobleme. Anfang der 1980er Jahre verschob sich das Hauptarbeitsgebiet dann auf Zuschnittsoptimierung und Packungsprobleme. Ausgangspunkt hierfür waren konkrete Anfragen aus der Holzindustrie.

Ein noch sehr einfach formulierbares eindimensionales Zuschnittsproblem ist: Man hat Material der Länge l vorliegen und möchte daraus Teile einer bestimmten Länge so zuschneiden, dass der Abfall minimiert wird. Die Anzahl der Teile ist dabei nicht fest vorgegeben. Mathematisch lässt sich das auf das sogenannte Rucksackproblem zurückführen. Typisch ist, dass eine Nebenbedingung (die Länge) auftritt und nur ganzzahlige Werte sinnvoll sind, also ein ganzahliges lineares Optimierungsproblem vorliegt.

Prinzipiell geht es im Rucksackproblem darum, dass man ein vorgegebenes Volumen des Rucksackes (seine Kapazität) gegeben hat, in das man beliebig verformbare Teile einpackt. In der Praxis so etwas wie Kleidung und Wanderutensilien, die man alle mehr oder weniger nötig braucht. Das heißt, jedes potentiell mitzunehmenden Teil hat zwei relevante Eigenschaften: Es braucht ein bestimmtes Volumen im Rucksack und es hat einen bestimmten Wert an Nützlichkeit. Das Problem ist gelöst, wenn man die Packung mit dem größten Nützlichkeits-Wert gefunden hat.

Theoretisch kann man natürlich alle Möglichkeiten durchgehen, den Rucksack zu packen und dann aus allen die nützlichste aussuchen, aber in der Praxis ist die Anzahl an Möglichkeiten für Packungen sehr schnell so groß, dass auch ein schneller Computer zu lange braucht, um alle Fälle in akzeptabler Zeit zu betrachten. Hier setzt die Idee des Branch-and-Bound-Verfahrens an. Der sogenannte zulässige Bereich, d.h. die Menge der Lösungen, die alle Bedingungen erfüllen, wird zunächst schrittweise in Teilbereiche zerlegt. Auf diesen Teilbereichen werden die Optimierungsprobleme gelöst und dann aus allen die beste Variante gesucht. Leider können dies extrem viele Teilprobleme sein, weshalb der "Bound"-Teil des Verfahrens versucht, möglichst viele der Teilprobleme von vornherein als nicht aussichtsreich zu verwerfen. Der Erfolg des Branch-and-Bound steht und fällt mit guten Ideen für die Zerlegung und die zugehörigen Schranken. Der Rechenaufwand ist für einen konkreten Fall jeweils schwer schätzbar.

Ein weiteres Verfahren für ganzzahlige Optimierungsprobleme ist Dynamische Optimierung. Ursprünglich wurde es für die Optimierung von sequentiellen Entscheidungsprozessen entwickelt. Diese Technik zur mehrstufigen Problemlösung kann auf Probleme angewendet werden, die als verschachtelte Familie von Teilproblemen beschrieben werden können. Das ursprüngliche Problem wird rekursiv aus den Lösungen der Teilprobleme gelöst. Deshalb ist der Aufwand pseudopolynomial und es erfordert etwa gleichen Rechenaufwand für gleich große Probleme.

Weitere Verfahren zur Lösung von ganzzahligen Optimierungsproblemen sind bekannt unter dem Namen Schnittebenenverfahren und Branch-and-Cut. Nach der Berechnung des Optimums der stetigen Relaxation werden Schritt für Schritt neue Nebenbedingungen zum Problem hinzugefügt. Mit Hilfe dieser zusätzlichen Ungleichungen werden nicht ganzzahlige Variablen der kontinuierlichen Lösungen gezwungen, ganzzahlige Werte anzunehmen. Oftmals ist eine Kombination mit einer Verzweigungsstrategie erforderlich.

Eine nahe liegende Verallgemeinerung des oben beschriebenen einfachsten Zuschnittsproblems ist der Zuschnitt von rechteckigen Teilen aus einer Spanplatte. In der Holzindustrie macht eine Kreissäge das meist mit Schnitten von einem Rand der Platte zum gegenüberliegenden. Das sind sogenannte Guillotine-Schnitte. Das trifft auch für Zuschnitt von Glas und Fliesen zu. Hier ist die Anpassung der eindimensionalen Algorithmen noch relativ einfach auf den zweidimensionalen Fall möglich. Richtig schwierig wird es aber, wenn beliebige Polygone als Teile auftreten oder gar solche mit krummlinigen Rändern.

Ein typisches Anwendungsproblem ist, dass eine optimale Anordnung von Einzelteilen eines Kleidungsstück auf einer Stoffbahn in der Regel nicht übertragbar auf eine andere Konfektionsgröße ist.

Eine weitere Familie von Fragestellungen ist: Wie groß muss ein Quadrat sein, um Platz für eine vorgegebene Anzahl von Kreise mit Durchmesser 1 zu bieten? Das ist mathematisch sehr einfach zu formulieren aber in der Regel schwierig zu lösen, da das zugehörige Optimierungsproblem nicht konvex ist.

Literatur und weiterführende Informationen

• Rucksackproblem
• Algorithmen für Rucksackproblem
• Rucksackproblem in Anwendungen
• Josef Kallrath: Gemischt-Ganzzahlige Optimierung. Modellierung in der Praxis. Vieweg/Springer 2013.
• Guntram Scheithauer: Zuschnitt- und Packungsoptimierung - Problemstellungen, Modellierungstechniken, Lösungsmethoden. Vieweg/Springer 2008.
• Guntram Scheithauer: Introduction to Cutting and Packing Optimization - Problems, Modeling Approaches, Solution Methods Springer 2018.

Podcasts

• M. Lübbecke: Operations Research, Gespräch mit S. Ritterbusch im Modellansatz Podcast, Folge 110, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2016. http://modellansatz.de/operations-research
• M. An: Topologieoptimierung, Gespräch mit G. Thäter im Modellansatz Podcast, Folge 125, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2017. http://modellansatz.de/topologieoptimierung
• K. Berude: Sensoreinsatzplanung, Gespräch mit S. Ritterbusch im Modellansatz Podcast, Folge 154, Fakultät für Mathematik, Karlsruher Institut für Technologie (KIT), 2018. http://modellansatz.de/sensoreinsatzplanung