Vorlesung: Anwendungen in der ganzzahligen Optimierung

Martin Grötschel

Vorlesung gehalten im Sommersemester 1998 am Fachbereich Mathematik der Technischen Universität Berlin - Erweiterte Inhaltsangabe mit Literaturverzeichnis

Kapitel 1 (22.4.98)

In diesem Kapitel wird ein kurzer Überblick über das Gesamtgebiet Optimierung (lineare, nichtlineare, stochastische, kombinatorische, ganzzahlige und gemischt-ganzzahlige Optimierung) gegeben. Es werden einige wichtige Resultate (notwendige und hinreichende Optimalitätsbedingungen, Dualitätssatz der linearen Programmierung, Kuhn-Tucker-Sätze) und bedeutende Algorithmen der linearen und nichtlinearen Optimierung (Simplexmethode, Newtonverfahren, BFGS-Verfahren, Subgradientenmethode, ...) kurz vorgestellt.

Kapitel 2: Modellierungsprobleme (22.4.98)

In diesem Kapitel wird anhand des Kapitels ``Alcuin's Transportation Problems and Integer Programming'' gezeigt, welche unterschiedlichen Möglichkeiten es gibt, praktische Aufgaben zu modellieren. Hierzu wird das (äußerst simple) Beispiel des Transportes von einem Wolf, einer Ziege und einem Kohlkopf herangezogen. Diese Aufgabe wird als ganzzahliges lineares Programm modelliert, wobei auf die verschiedenen Möglichkeiten, praktische Fragestellungen zu modellieren, eingegangen wird. Anhand dieses konkreten Beispiels wird nochmals die Branch&Bound-Methode erläutert, und es werden Grundzüge der Schnittebenentheorie erklärt. Gleichzeitig wird auf die Bedeutung einer verständlichen Modellierung für die Praxis hingewiesen, und es wird die ``psychologische Dimension'' der Zusammenarbeit mit Personen aus der Praxis erläutert.

Kapitel 3: Löcherbohren und Maskenzeichnen, das Travelling Salesman und das Rural Postman Problem (29.4.98 und 13.5.98)

Dieses Kapitel basiert auf dem Buch

Gerhard Reinelt: The Travelling Salesman Problem: Computational Solutions for TSP Applications, Lecture Notes in Computer Science 840, Springer-Verlag, 1994

sowie den Artikeln

Martin Grötschel & Olaf Holland: Solution of Large-Scale Symmetric Travelling Salesman Problems, Mathematical Programming 51 (1991) 141--202

Martin Grötschel, Michael Jünger & Gerhard Reinelt: Optimal Control of Plotting and Drilling Machines: A Case Study, ZOR -- Methods and Models of Operations Research 35 (1991) 61--84

In diesem Kapitel wird die Modellierung einfacher numerisch kontrollierter Maschinen erläutert. die Aufgabe, in eine Leiterplatte vorgegebene Löcher mit Hilfe einer mechanischen, numerisch gesteuerten Bohrmaschine zu bohren, führt zu einem Travelling Salesman Problem mit einer (komplizierten) Zielfunktion. Das Problem, Masken für die lithographische Herstellung von Leiterplatten zu zeichnen, sieht zunächst wie ein Travelling Salesman Problem aus, ist jedoch eine Kombination von mehreren Travelling Salesman Problemen, mehreren Rural Postman Problemen und einem sehr speziellen Reihenfolgeproblem Diese beiden Probleme kommen bei jedem Hersteller von Leiterplatten in großer Anzahl vor. Hier wird berichtet über einen Anwendungsfall bei der Firma Siemens. Die in diesem Projekt eintwickelten Algorithmen laufen seit etwa 10 Jahren bei Siemens in Augsburg und Karlsruhe. Die modellierungstechnischen Probleme, die insbesondere beim Maskenszeichnen auftreten, werden eingehend erklärt, und es werden die mathematischen Methoden erläutert, mit denen die Aufgaben in der Praxis gelöst wurden. Für die Praxis waren exakte Optimierungsverfahren nicht geeignet, da die Praxisprobleme in sehr kurzer Zeit auf kleinen Rechnern gelöst werden mußten und die Probleme zum Teil so groß waren, daß sie auch in hunderten von Stunden Rechenzeit nicht optimal gelöst werden können.

Kapitel 4: Umrüstzeiten für Rotationsdruckmaschinen (6.5.98)

Die Reihenfolgeplanung für Druckmaschinen ist ein sehr häufig vorkommendes Optimierungsproblem. Hier beschäftigen wir uns konkret mit der Modellierung eines Systems von zwei komplexen Rotatitonsdruckmaschinen, die bei der Firma Herlitz zum Drucken von Geschenkpapier eingesetzt werden. Die Firma macht in der Regel eine Wochenplanung für die anstehenden Druckaufträge und versucht dabei, die Druckaufträge so auf die beiden Maschinen zu verteilen, daß die notwendigen Umrüstzeiten (Auswechseln von Walzen, Reinigung von Walzen und der Druckmaschine selbst, Justieren, ...) insgesamt so wenig Zeit wie möglich erfordern. Dabei sind eine Reihe von komplizierten technischen Nebenbedingungen zu berücksichtigen. Insbesondere geht es auch darum, die Reihenfolge so zu planen, daß das Wechseln der Farben für die einzelnen Druckwalzen nicht zuviel Aufwand erfordert. Hierbei sind unter anderem (empirische) Farbtabellen zu berücksichtigen, die darüber Auskunft geben, aus welcher Farbe welche andere Farbe durch Hinzugabe von anderen Farbbestandteilen gemischt werden kann.

Kapitel 5: Ising-Modelle von Spingläsern, Via-Minimierung, das Max-Cut-Problem und binäre Matroide (13.5.98)

Kapitel 6: Das Chinesische Postboten-Problem, das Max-Cut-Problem in planaren Graphen (20.5.98)

Kapitel 7: Glückwunschkartenkommissionierung (27.5.98)

Besuch bei der Firma Herlitz: Innerbetriebliche Logistik (3.6.98)

Kapitel 8: Kombinatorische Optimierung in Vekehr und Transport (10.6.98)

Kapitel 9: Optimierung eines Hochregallagers (17.6.98)