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\xfcr waren konkrete Anfragen aus der Holzindustrie. Ein noch sehr einfach formulierbares eindimensionales Zuschnittsproblem ist: Man hat Material der L\xe4nge l vorliegen und m\xf6chte daraus Teile einer bestimmten L\xe4nge so zuschneiden, dass der Abfall minimiert wird. Die Anzahl der Teile ist dabei nicht fest vorgegeben. Mathematisch l\xe4sst sich das auf das sogenannte Rucksackproblem zur\xfcckf\xfchren. Typisch ist, dass eine Nebenbedingung (die L\xe4nge) 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\xe4t) 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\xf6tig braucht. Das hei\xdft, jedes potentiell mitzunehmenden Teil hat zwei relevante Eigenschaften: Es braucht ein bestimmtes Volumen im Rucksack und es hat einen bestimmten Wert an N\xfctzlichkeit. Das Problem ist gel\xf6st, wenn man die Packung mit dem gr\xf6\xdften N\xfctzlichkeits-Wert gefunden hat. Theoretisch kann man nat\xfcrlich alle M\xf6glichkeiten durchgehen, den Rucksack zu packen und dann aus allen die n\xfctzlichste aussuchen, aber in der Praxis ist die Anzahl an M\xf6glichkeiten f\xfcr Packungen sehr schnell so gro\xdf, dass auch ein schneller Computer zu lange braucht, um alle F\xe4lle in akzeptabler Zeit zu betrachten. Hier setzt die Idee des Branch-and-Bound-Verfahrens an. Der sogenannte zul\xe4ssige Bereich, d.h. die Menge der L\xf6sungen, die alle Bedingungen erf\xfcllen, wird zun\xe4chst schrittweise in Teilbereiche zerlegt. Auf diesen Teilbereichen werden die Optimierungsprobleme gel\xf6st und dann aus allen die beste Variante gesucht. Leider k\xf6nnen dies extrem viele Teilprobleme sein, weshalb der "Bound"-Teil des Verfahrens versucht, m\xf6glichst viele der Teilprobleme von vornherein als nicht aussichtsreich zu verwerfen. Der Erfolg des Branch-and-Bound steht und f\xe4llt mit guten Ideen f\xfcr die Zerlegung und die zugeh\xf6rigen Schranken. Der Rechenaufwand ist f\xfcr einen konkreten Fall jeweils schwer sch\xe4tzbar. Ein weiteres Verfahren f\xfcr ganzzahlige Optimierungsprobleme ist Dynamische Optimierung. Urspr\xfcnglich wurde es f\xfcr die Optimierung von sequentiellen Entscheidungsprozessen entwickelt. Diese Technik zur mehrstufigen Probleml\xf6sung kann auf Probleme angewendet werden, die als verschachtelte Familie von Teilproblemen beschrieben werden k\xf6nnen. Das urspr\xfcngliche Problem wird rekursiv aus den L\xf6sungen der Teilprobleme gel\xf6st. Deshalb ist der Aufwand pseudopolynomial und es erfordert etwa gleichen Rechenaufwand (...)