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