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)