Ausgewählte Kapitel aus der ganzzahligen Optimierung
* Inhalt der Vorlesung
* Termine
* Zielgruppe und Voraussetzungen
* Anmeldung
* Aktuelle Teilnehmerliste
* Geplante Fortsetzung: Blockseminar Ganzzahlige Optimierung
(28.-30. Januar 2000)
Inhalt
In vielen Wachstumsbranchen der Industrie wird moderne Mathematik als
Schlüsseltechnologie zur Lösung drängender Probleme
angesehen. Insbesondere
Optimierung spielt hier eine zunehmend wichtige Rolle. In der geplanten
Blockveranstaltung wird dies am Beispiel der ganzzahligen Optimierung
demonstriert. Die Vorlesung führt in besonders interessante Anwendungsfelder
ein. Dazu zählen:
* Transport und Verkehr (unter anderem Umlauf-, Fahrzeug-
und
Fahrereinsatzplanung im öffentlichen
Nahverkehr)
* Online-Optimierung (insbesondere bei innerbetrieblicher
Logistik)
* Telekommunikation (kostengünstiger Entwurf ausfallsicherer
Netze,
Frequenzzuweisung im Mobilfunk, etc.)
In der Vorlesung werden diese Problembereiche dargestellt und mathematisch
modelliert. Firmenbesuche werden den Einblick in die Praxis ergänzen.
Wichtigster Bestandteil der Vorlesung ist die Entwicklung der mathematischen
Theorien, auf denen die Methodik zur Lösung der Probleme beruht:
* Lösen großer Linearer Programme (Spaltengenerierung,
Pricing)
* Polyedertheorie (Beweistechniken der polyedrischen Kombinatorik)
* Allgemeine ganzzahlige Programme (Schnittebenen, Branch&Bound,
Branch&Cut)
* Graphentheorie (Zusammenhang, Stabile Mengen, Färbungen)
* Online-Optimierung (Kompetitive Analyse, randomisierte
Algorithmen,
Stochastik)
Weiterhin werden für die Praxis wichtige Implementierungs- und
Simulationstechniken vorgestellt. Die Lösungsalgorithmen werden
eingehend
besprochen. In den Übungen wird der Vorlesungsstoff vertieft;
insbesondere
sollen hier auch Modellierungsaufgaben gelöst werden.
Termine
Vorlesung und Übungen sind in Form einer integrierten Blockveranstaltung
organisiert, die vom 11. bis 24. Oktober 1999 an 11 Tagen stattfindet.
| Vorlesungen | 11.-16. Oktober, 18. Oktober 1999 | 9:00-11:00 |
| 21.-24. Oktober | 14:00-17:00 | |
| 9:00-11:00 | ||
| 14:00-17:00 | ||
| Übungen | 11.-16. Oktober, 18. Oktober 1999 | 11:00-12:00 |
| 17:00-18:00 | ||
| 21.-24. Oktober | 11:00-12:00 | |
| 17:00-18:00 | ||
| Besuch HHLA Hamburg | 18. Oktober | ganztägig |
| Besuch Herlitz AG | 21. Oktober | nachmittags |
Anrechenbarkeit: 4+2 Semesterwochenstunden
Schein: Teilnahmebescheinigungen werden vergeben
Zielgruppe und Voraussetzungen
Die Veranstaltung richtet sich an Studenten der Mathematik und der Techno-
und Wirtschaftsmathematik, die Grundkenntnisse der Linearen und Ganzzahligen
Optimierung besitzen. Insbesondere ist an Studenten gedacht, die sich
auf
eine Diplomarbeit oder eine Promotion in diesem Themenbereich vorbereiten
wollen. Diese Veranstaltung ist in Inhalt und Form ein Experiment.
Falls
dieses sich bewährt, sollen in Zukunft ähnliche Veranstaltungen
auch zu
anderen mathematischen Themenkreisen stattfinden und das übliche
Vorlesungsprogramm ergänzen.
Geplante Fortsetzung
Als Fortsetzung der Veranstaltung findet ein Blockseminar Ganzzahlige
Optimierung vom 28. bis 30. Januar 2000 statt. Themen hierzu werden
nach
Beendigung der Blockvorlesung ausgegeben.
Eine Vorbesprechung findet am 8. Dezember 1999 um 15.45 Uhr im Raum
MA 005 im Anschluß an die COMA-Vorlesung statt.
Geplante Themen:
Transport und Verkehr (TV)
1. Asymmetrisches Travelling-Salesperson-Problem
mit Zeitfenstern.
2. Asymmetrisches Travelling-Salesperson-Problem
mit Präzedenzen.
3. Mehrgüterflüsse.
4. Set-Partitioning und Spaltengenerierung.
Online-Optimierung (OO)
1. Scheduling auf parallelen Maschinen im
Sequenzmodell.
2. Scheduling auf parallelen Maschinen im
Zeitstempelmodell.
3. Travelling-Salesperson-Problem.
4. Auftragsannahme und Lieferterminzusage.
Telekommunikation (TK)
1. Graphenfärbung.
2. Frequenzzuweisung im Mobilfunk.
3. k-Partitionierungsproblem und semidefinite
Programmierung.
4. Graphenzusammenhang und ausfallsichere
Netze.
Zeitplanung der BLOCKVORLESUNG:
Morgens wurden zwei, nachmittags jeweils drei Zeitstunden Vorlesung
gehalten; morgens und nachmittags jeweils eine Zeitstunde
Übungen. Das grundsätzliche Ablaufschema:
| morgens: | V 9 - 11 |
| UE 11 - 12 | |
| nachmittags: | V 13:30 - 16:30 |
| UE 16:30 - 17:30 |
wurde jedoch "dynamisch" dem jeweiligen Thema angepasst, Übungen
wurden also dann eingeschoben, wenn ein Themenkreis abgeschlossen
war oder es aus anderen Gründen sinnvoll erschien.
Inhaltsübersicht
Kapitel 0: Modellierung praktischer Probleme: allgemeine
Bemerkungen
Kapitel 1: Transport und Verkehr
Themenkreis 1.1: praktisches Problem: Rufbussysteme
mathematische Probleme: Set Packing/stabile Mengen,
polyedrische Kombinatorik, perfekte Graphen
Themenkreis 1.2: praktisches Problem: Dienstplanung
mathematische Probleme: Set-Partitioning und -Covering
Themenkreis 1.3: praktisches Problem: Umlaufplanung
mathematische Probleme: Netzwerkfluss-Theorie,
Mehrgüter-Flüsse
Kapitel 2: Online-Optimierung
Themenkreis 2.1: Einführung in die kompetitive Analyse, k
lassische Beispiele
Themenkreis 2.2: Fortgeschrittene Analysemethoden:
Access-Graph-modell, Amortisierte Analyse, Approximation
metrischer Räume
Themenkreis 2.3: Schwierige Problemklassen:
Online-Netzwerk-Routing, Scheduling, kantendisjunkte Wege
Themenkreis 2.4: Zeitstempelmodell: Dial-a-Ride-Probleme
Themenkreis 2.5: Vertretbare Belastung
Themenkreis 2.6: Diskrete ereignisbasierte Simulation
Themenkreis 2.7: praktische Projekte
Kapitel 3: Steuerung von CNC-Maschinen
Themenkreis 3.1: praktisches Problem: Steuerung eines Leiterplatten-
Bohrautomaten
mathematisches Problem: symmetrisches Travelling-
Salesman-Problem
Themenkreis 3.2: praktisches Problem: Steuerung von Laser-
Zeichengeräten
mathematische Probleme: symmetrisches TSP und
Rural-Postman-Problem
Themenkreis 3.3: praktisches Problem: Umrüstzeitenminimierung
für
Rotationsdruckmaschinen
mathematisches Problem: k-TSP
Kapitel 4: Telekommunikation
Themenkreis 4.1: Allgemeine Übersicht über mathematische
Probleme
in der Telekommunikation insbesondere im Mobilfunk
Themenkreis 4.2: praktisches Problem: Frequenzplanung im Mobilfunk
mathematische Probleme: Knotenfärbung in Graphen,
Listen- und T-Färbungsprobleme, einbettbare Graphen
Themenkreis 4.3: praktisches Problem: kostengünstiger Entwurf
ausfallsicherer Telekommunikationsnetze
mathematische Probleme: kürzeste Wege mit Nebenbedingungen,
aufspannende Bäume, allgemeine Zusammenhangsprobleme in
Graphen, Matching- und Matroidtheorie, Packen von
Arboreszenzflüssen
Montag, 11. Oktober 1999:
V morgens:
Kapitel 0: Modellierung praktischer Probleme: allgemeine Bemerkungen
Wie modelliert man praktische Probleme in Transport und Verkehr
als ganzzahlige Optimierungsprobleme? Vortrag anhand des
"Alcuin-Papers (SC 95-27). Dabei werden diskutiert:
- verschiedene Modellierungen
- verschiedene Zielfunktionen
- Die Programme PORTA (Berechnung verschiedener Darstellungen
von Polyedern) und CPLEX (LP-Löser) werden
vorgeführt
(durch Ralph Borndörfer)
UE morgens: Modellierung eines weiteren Alcuin-Problems
(durch Diana Poensgen)
V nachmittags:
Kapitel 1: Transport und Verkehr
Themenkreis 1.1: praktisches Problem: Rufbussysteme
mathematische Probleme: Set Packing/stabile Mengen,
polyedrische Kombinatorik, perfekte Graphen
Optimierung des Anrufsammeltaxi-Systems in Passau
Telebus: Das praktische Probleme, organisatorische Aufgaben
soziales
und politisches Umfeld,
mathematische
Modellierung
Einführung von:
Set Partitioning
Set Packing
Set Covering
Das Stabile-Mengen-Polytop (Facetten, Separierungsverfahren)
UE nachmittags: Vorlesung weitergeführt
Dienstag, 12. Oktober 1999:
V morgens:
Der polyedrische Ansatz zur Lösung des Stabile-Mengen-Problems
Perfekte Graphen: Charakterisierungen, Beispiele
Orthonormale
Repräsentationen von Graphen und
orthonormal
representation constraints
Die Primal-Duale Gleichungs- und Ungleichungskette für
das
gewichtete Stabile-Mengen-Problem und das gewichtete
Cliquenüberdeckungsproblem
Stabile Mengen und Blockcodes
UE morgens (Annegret Wagler):
Klassen verschiedener perfekter Graphen (bipartite Graphen, Intervallgraphen
Anwendungen der Sätze von König zu bipartiten Graphen
und des Satzes
von Dillworth, totale Unimodularität von Matrizen mit der
consecutive-
ones property)
minimal und kritisch imperfekte Graphen
V nachmittags:
Themenkreis 1.2: praktisches Problem: Dienstplanung
mathematische Probleme: Set-Partitioning und -Covering
Dienstplanung als Set Partitioning mit Nebenbedingungen
Darstellung des Projektes mit IVU, HanseCom und BVG
UE nachmittags (Birgit Grohe):
Algorithmus von Wedelin und Varianten (Heuristiken für große
Set-Partitioning-Probleme)
Mittwoch, 13. Oktober 1999:
V morgens:
Beweistechniken der polyedrischen Kombinatorik:
Dimensionsbeweise, Facettenbeweise, Vollständigkeitsbeweise,
vorgeführt anhand von Matroidpolytopen, Stabile-Mengen-Polytopen
und dem Travelling-Salesman-Polytop
Themenkreis 1.3: praktisches Problem: Umlaufplanung
mathematische Probleme: Netzwerkfluss-Theorie,
Mehrgüter-Flüsse
Übersicht über Netzwerkfluss-Theorie: maximale Flüsse,
Max-Flow Min-Cut Theorem, Totale Unimodularität der
zugehörigen Matrix, Flüsse mit minimalen Kosten,
Mehrgüter-Flüsse.
UE morgens:
Napkin-Problem und Nurse-Problem, weitere Anwendungen
der Fluss-Theorie (Sven Krumke)
V nachmittags:
Einführung in die Fahrzeugumlaufplanung im ÖPNV, Modellierung
des
Busumlaufproblems bei der BVG, Darstellung des algorithmischen
Ansatzes, zugehörige Rechentechnik
Überblick: Mathematik und Transport (Basis: Engelberg-Paper,
SC 98-09)
UE nachmittags: Diskussion der mathematischen Modellierung
des Umlaufplanungsproblems
Donnerstag, 14. Oktober
V morgens:
Kapitel 2: Online-Optimierung
Themenkreis 2.1: Einführung in die kompetitive Analyse, klassische Beispiele
- kompetitive Analyse als Beurteilungswerkzeug für Online-Algorithmen,
Skirental-Problem: wie lange soll man Ski leihen, wann kaufen?
Paging: welche Seite soll bei einem Cache-Miss aus dem Cache entfernt
werden
BahnCard-Problem: wann soll man eine BahnCard kaufen?
UE morgens:
- Online-Bin-Packing: FirstFit-Algorithmus, untere Schranken
- Page-Replication: Wann soll eine Datenbank (unter Kosten) in einem
Computernetz an eine günstigere Stelle kopiert werden, um die
Zugriffskosten zu reduzieren?
V nachmittags:
Themenkreis 2.2: Fortgeschrittene Analysemethoden: Access-Graph-modell,
Amortisierte Analyse, Approximation metrischer
Räume
- Paging: Algorithmen FIFO, LIFO, LRU (Least Recently Used), Kompetitivitätsresultate
für Markierungsalgorithmen,
Access-Graph-Modell;
- k-Server-Problem: Welcher Server soll in einem metrischen Raum zu
einer Serviceanforderung bewegt werden?
k-Server-Vermutung, Spezialfall reele Gerade
UE nachmittags:
- Anwendung Amortisierte Analyse: amortisierte Kosten von Stackoperationen
- Anwendung Approximation metrischer Räume: k-Server Problem auf
einem Kreis.
Freitag, 15. Oktober
V morgens:
Kapitel 2: Online-Optimierung
Themenkreis 2.3: Schwierige Problemklassen: Online-Netzwerk-Routing, Scheduling
- Online-Netzwerk-Routing: Annahme oder Ablehnung von Routing-Anfragen
unter der Annahme, daß eine Mindestbandbreite im
Netz zur Verfügung steht
UE morgens:
- Online-Parallel-Machine-Scheduling: Minimiere die Gesamtfertigstellungszeit
durch online-Zuweisung von Jobs auf m parallele
identische Maschinen, Graham-Algorithmus, Albers-Algorithmus
V nachmittags:
Themenkreis 2.4: Zeitstempelmodell: Dial-a-Ride-Probleme (OLDARP)
- Aufträge erhalten Zeitstempel, der Online-Algorithmus darf Aufträge
sammeln;
- OLDARP: In welcher Reihenfolge soll ein Transportfahrzeug Transportaufträge
abarbeiten? Kapazität Eins, Minimierung der
Gesamtfertigstellungszeit, Algorithmen REPLAN, IGNORE.
UE nachmittags:
- Beweis: Algorithmus SMARTSTART ist 2-kompetitiv (bestmöglich)
Samstag, 16. Oktober
V morgens:
Themenkreis 2.5: Vertretbare Belastung
- OLDARP: Minimiere maximale Flußzeit, kompetitive Analyse liefert
keine Information, Definition vertretbare Belastung, IGNORE
liefert beschränkte maximale Flußzeit
UE morgens:
- Beispiel mit unbeschränkter maximaler Flußzeit für REPLAN
V nachmittags:
Themenkreis 2.6: Diskrete ereignisbasierte Simulation (DES)
- Vorführung Fahrstuhlsimulation
- Struktur von DES-Programmen
Themenkreis 2.7: praktische Projekte
- Leerfahrtminimale Steuerung von Regalbediengeräten, Modellierung
als online asymmetrisches Travelling-Saleman-Problem,
Offline-Problem mit Zeitfenstern, a-posteriori-Analyse, Bericht der
Verbesserungen in der Praxis durch Optimierung
- Zuordnung von Aufträgen auf Kommissionierfahrzeuge, Modellierung
durch online Commissioning-Vehicle-Problem zur
Minimierung der Gesamtanzahl der Stoppositionen, in der Praxis unbefriedigende
Kompetitivitätsresultate, Simulationsergebnisse,
Verbesserungen durch Heuristiken wie Greedy+2OPT, Bericht über
Einsparmöglichkeiten in der Praxis
UE nachmittags:
- 0-1-Challenge-Auswertung: Man gebe eine möglichst zufällige
Folge von 1000 Nullen und Einsen ein; man errate möglichst viele
Eingaben der Gegenspieler
Montag, 18. Oktober:
7 Uhr Abfahrt vor dem Mathematikgebäude der TU Berlin
nach Hamburg
11 Uhr Eintreffen am Burchardkai der Hamburger Hafen und
Lagerhaus AG (HHLA)
Rundfahrt und Besichtigung des
Container-Terminals
der HHLA (Führung durch die
Herren Mölck und
Wölfer, HHLA)
12 Uhr Vortrag (mit Diskussion) von Herrn Wölfer über Basisdaten
und Optimierungsaspekte des Container-Terminals
Burchardkai
sowie über die Planungen
zum Container-Terminal
Altenwerder (Gegenüberstellung
der verschiedenen
Logistigkonzepte: Van Carrier,
Transtainer, Automatically
Guided Vehicles, etc.)
14 Uhr gemeinsames Mittagessen bei der HHLA
15 Uhr Rückfahrt nach Berlin
19 Uhr Ankunft an der TU Berlin
Donnerstag, 21. Oktober:
V morgens:
Kapitel 3: Steuerung von CNC-Maschinen
Themenkreis 3.1: praktisches Problem: Steuerung eines Leiterplatten-
Bohrautomaten
mathematisches Problem: symmetrisches Travelling-
Salesman-Problem
- Steuerung eines Leiterplatten-Bohrautomaten: Modellierung
und Formulierung als symmetrisches Travelling-Salesman-
Problem, Bericht über die Ergebnisse eines
Projekts
mit der Firma Siemens.
Themenkreis 3.2: praktisches Problem: Steuerung von Laser-
Zeichengeräten
mathematische Probleme: symmetrisches TSP und
Rural-Postman-Problem
- Steuerung von Laser-Geräten zum Zeichnen von Leiterplatten-
Masken: Modellierung als Folge von symmetrischen
Travelling-Salesman-Problemen, von Rural-Postman-Problemen,
und einem Scheduling-Problem, Bericht über
die Ergebnisse
eines Projekts mit der Firma Siemens.
Themenkreis 3.3: praktisches Problem: Umrüstzeitenminimierung
für
Rotationsdruckmaschinen
mathematisches Problem: k-TSP
- Umrüstzeitenminimierung für Rotationsdruckmaschinen
zum Drucken von Geschenkpapier, Modellierung als
asymmetrisches 2-Salesman-Problem, Bericht über
die
Ergebnisse eines Projekts mit der Firma Herlitz.
Besuch bei der Firma Herlitz in Falkensee
13 Uhr Abfahrt von ZIB
14 Uhr Eintreffen bei der Firma Herlitz, Vortrag von
Herrn Eckle zu Grunddaten der
Firma Herlitz,
zur Informationstechnik bei Herlitz
und zum
Logistik-Konzept.
15 Uhr Rundgang durch das Herlitz Logistik-Zentrum,
Führung durch die Herren
Eckle und Rüstau
17 Uhr Abschlussdiskussion
Freitag, 22. Oktober:
V morgens:
Kapitel 4: Telekommunikation
Themenkreis 4.1: Allgemeine Übersicht über mathematische
Probleme
in der Telekommunikation insbesondere im Mobilfunk
Überblick über Telekommunikationsnetzwerke (Mobilfunk
und Festnetztelefonie) und mathematische Aufgaben beim
Entwurf, Betrieb und der Kontrolle derartiger Netze
Funknetzplanung: Frequenz-, Standort-, Kapazitätsplanung
Wellenausbreitungsberechnung
Festnetzplanung: Topologie-, Kapazitäts- und Routenplanung
Sicherheitsplanung: Sicherungsmechanismen bei Ausfällen,
Kryptographie und Planung anderer
Datensicherheitsmechanismen
Tarifierung: Modellentwicklung
Marketing: Kundenanalyse und -prognose
Themenkreis 4.2: praktisches Problem: Frequenzplanung im Mobilfunk
mathematische Probleme: Knotenfärbung in Graphen,
Listen- und T-Färbungsprobleme, einbettbare Graphen
Einführung in die Frequenzplanung, Frequenzplanung als
Knotenfärbungsproblem und als List-Knotenfärbungsproblem
Einführung in die Färbungstheorie
V nachmittags:
Überblick über die wichtigste Resultate zur Knotenfärbung
(inclusive Theorie der planaren Graphen): k-farbenkritische
Graphen, Brooks' Theorem und Verallgemeinerungen (z. B.
von Thomassen auf Listen-Färbungsprobleme), Fünffarbensatz,
Satz von Grötzsch, Hajos- und Hadwiger-Vermutung, Resultate
zur Färbungszahl von Graphen, die auf Flächen höheren
Geschlechts eingebettet werden können: Heawood etc.
Algorithmische Aspekte der Färbungstheorie (sequential
colouring Heuristik, etc.).
(Handbook-Artikel von Toft, Buch von Toft und Jensen, Bondy&Murty,
2 Thomassen-Paper)
Detaillierte Beschreibung der Frequenzplanung bei E-Plus:
zwei mathematische Modelle und die Misserfolge bei der
Bestimung unterer Schranken.
Heuristiken und exakte Verfahren, Ergebnisse des Projektes
mit E-Plus sowie eingehende Diskussion (Andreas Eisenblätter)
Samstag, 23. Oktober:
V morgens:
Themenkreis 4.3: praktisches Problem: kostengünstiger Entwurf
ausfallsicherer Telekommunikationsnetze
mathematische Probleme: kürzeste Wege mit Nebenbedingungen,
aufspannende Bäume, allgemeine Zusammenhangsprobleme in
Graphen, Matching- und Matroidtheorie, Packen von
Arboreszenzflüssen
Projekte mit BellCore: Ausfallsichere LATA-Netzwerke,
Ausrüstung von Schiffen mit ausfallsicheren Glasfasernetzwerken,
dabei behandelt:
Polytop der kürzesten Wege, Polytop der zusammenhängenden
Untergraphen (Rückführung auf Matroid-Theorie), Matching-
Polytop und seine Verallgemeinerungen (b-Matching,
perfekt und nicht perfekt, mit und ohne Kantenkapazitäten),
r-Cover-Polytop (abgeleitet aus dem kapazitierten b-Matching
Polytop)
UE nachmittags:
Modellierung eines Punkt-zu-Mehrpunkt
Funksystems (der letzte Kilometer zum Kunden
ohne Kabel)
V nachmittags:
MULTISUN-Projekt: Ausbau des norwegischen Telekommunikationsnetzes
bei Berücksichtigung verschiedener Technologien und unter
Beachtung von Ausfallsicherheit
Ausführliche Darstellung des DISCNET-Modells für die
Planung des
E-Plus-Festnetzes (unter Einbeziehung von verfügbaren/anmietbaren
diskreten Kapazitäten auf den Kanten und einer detaillierten
Routenplanung)
Sonntag, 24. Oktober:
V morgens:
Modellierung des B-WIN-Problems: kostengünstige Auslegung
des vom DFN-Verein betriebenen Breitband-Wissenschaftsnetzes,
dabei zu beachten: IP-Routing mit dem OSPF-Routingprotokoll
(Paketversendung entlang kürzester Wege), auch in Ausfallsituationen
(Ausfall einer Kante oder eines Netzknotens), kürzeste
Wege
müssen beschränkte Länge haben, Ausfallsicherung
ist
durch 2-fachen Zusammenhang des Netzes zu gewährleisten,
die durchschnittliche Länge der Netzkanten darf einen
vorgegebenen Wert nicht überschreiten, die Anzahl der
Netzkanten ist vorgegeben, die Kostenfunktion ist eine
komplizierte von vielen Parametern abhängige Treppenfunktion
Kürzeste disjunkte Wege mit Längenbeschränkungen
V nachmittags:
Vermittlungs- und Transportnetzplanung bei der Austria-Telekom:
eine Übersicht über die dabei auftretenden kombinatorischen
Optimierungsprobleme (u.a. Standortplanung für Vermittlungs-
stellen, Auflösung von Netzhierarchien, Sicherheitsplanung,
Planung optischer Netze mit neuer Switching-Technologie)
Forschungs- und Entwicklungsplanung von Firmen (und damit
zusammenhängende mathematische und nicht-mathematische
Probleme)
am Beispiel der Firma Siemens (Siemens F&E Roadmaps)
UE nachmittags:
Auswertung und Diskussion der Programme zum 01-Wettbewerb
(im Restaurant Luise neben der U-Bahnstation Dahlem-Dorf)
Literatur:
Wenn in der nachfolgenden Liste eine Referenz des Typs SC JJ-AB
auftritt, so handelt es sich um ein Preprint, das am Konrad-Zuse-
Zentrum für Informationstechnik Berlin erstellt wurde. Derartige
Preprints sind über den WWW- Server des ZIB elektronisch
erhältlich (auf der Seite Veröffentlichungen mit der URL
http://www.zib.de/bib/pub/index.de.html einfach auf "Preprints und
Technical Reports des ZIB klicken). Daher sind die SC-Nummern auch
dann
angegeben, wenn die betreffenden Preprints bereits in einer Zeitschrift
etc. veröffentlicht wurden. Ein Preprint unterscheidet sich manchmal
(geringfügig) von der veröffentlichten Version des Papers.
einführende Bücher zur ganzzahligen Optimierung:
Laurence Wolsey: Integer Programming, Wiley,
Chichester 1998
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver:
Combinatorial Optimization, Wiley, New York, 1998
vertiefende Bücher zur Theorie:
Alexander Schrijver: Theory of Linear and Integer Programming,
Wiley, Chichester, 1998
Martin Grötschel, Laszlo Lovasz, Alexander Schrijver: Geometric
Algorithms and Combinatorial Optimization, Springer,
Berlin, 1993
Einführung in die Graphentheorie:
J. A. Bondy, U. S. R. Murty: Graph Theory with Applications
Macmillan, London, 1976
weitere, in der Vorlesung benutzte Literatur:
R. K. Ahuja, T. L. Magnanti, J. B. Orlin: Network Flows: Theory,
Algorithms, and Applications Prentice-Hall, Englewood Cliffs (1993)
Dimitris Alevras, Martin Grötschel, Roland Wessäly: Capacity
and
Survivability Models for Telecommunication Networks, SC 97-24
veröffentlicht in: Proceedings of the EURO XV/INFORMS XXXIV Meeting,
Barcelona, Spanien, 1997
Dimitris Alevras, Martin Grötschel, Roland Wessäly: Cost-Efficient
Network Synthesis from Leased Lines, SC 97-22, veröffentlicht
in:
Annals of Operations Research 76, 1998, 1-20
Dimitris Alevras, Martin Grötschel, Roland Wessäly: A Network
Dimensioning Tool, SC 96-49
Dimitris Alevras, Martin Grötschel, Peter Jonas, Ulrich Paul,
Roland Wessäly: Survivable Mobile Phone Architectures: Models
and
Solution Methods, SC 96-48, veröffentlicht in: IEEE Communications
Magazine, March 1998, 88-93
Andreas Bley, Martin Grötschel, Roland Wessäly: Design of
Broadband
Virtual Private Networks: Model and Heuristics for the B-WiN, SC 98-13
Ralf Borndörfer: Aspects of Set Packing, Partitioning, and Covering,
Shaker Verlag, Aachen 1998 (ISBN 3-8265-4351-3)
Ralf Borndörfer, Martin Grötschel, Andreas Löbel: Alcuins
Transportation Problems and Integer Programming, veröffentlicht
in:
P. L. Butzer et al.: 1200 Years of Arts and Science in Central
Europe, Band II, Thouet Verlag, Aachen, 379-409 (1998) SC 95-27
Ralf Borndörfer, Martin Grötschel, Fridolin Klostermeier,
Christian
Küttner: Telebus Berlin - Mobilität für Behinderte,
SC 96-40
veröffentlicht in: Der Nahverkehr, 1-2/97:20-22
Ralf Borndörfer, Martin Grötschel, Werner Herzog, Fridolin
Klostermeier, Wilhelm Konsek, Christian Küttner: Kürzen muß
nicht Kahlschlag
heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin, SC
96-41
Ralf Borndörfer, Martin Grötschel, Fridolin Klostermeier,
Christian
Küttner: Optimierung des Berliner Behindertenfahrdienstes, SC
97-10
veröffentlicht in: DMV-Mitteilungen, 2/97, 38-43
Ralf Borndörfer, Martin Grötschel, Fridolin Klostermeier,
Christian
Küttner: Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System
SC 97-23
Ralf Borndörfer, Andreas Löbel, Uwe Strubbe, Manfred Völker:
Zielorientierte Dienstplanoptimierung, SC 98-41
Ralf Borndörfer, Andreas Eisenblätter, Martin Grötschel,
Alexander Martin: The Orientation Model for Frequency
Assignment Problems, TR 98-01
Ralf Borndörfer, Andreas Eisenblätter, Martin Grötschel,
Alexander
Martin: Frequency Assignment in Cellular Phone Networks, SC 97-35
Ralf Borndörfer, Martin Grötschel, Andreas Löbel: Der
Schnellste
Weg zum Ziel, SC 99-32
Ralf Borndörfer, Martin Grötschel, Andreas Löbel: Optimization
of
Transportation Systems, SC 98-09, veröffentlicht in: Acta Forum
Engelberg 1998, The Future of Mobility & Transportation in a Moving
World, Ed. VDF Hochschulverlag AG an der ETH Zürich
Daxlberger, Christian: Umrüstzeitenminimierung für
Rotationsdruckmaschinen, Diplomarbeit, TU Berlin,
Oktober 1998
Martin Grötschel, Laszlo Lovasz, Alexander Schrijver: Geometric
Algorithms and Combinatorial Optimization, Springer, Berlin, 1993,
Kapitel 9
Martin Grötschel: My Favorite Theorem: Characterizations of Perfect
Graphs, SC 99-17, veröffentlicht in: Optima 62 91999) 2-5
Martin Grötschel, Andreas Löbel, Manfred Völker: Optimierung
des
Fahrzeugumlaufs im öffentlichen Nahverkehr, SC 96-08 veröffentlicht
in: K.-H. Hoffmann, W. Jäger, T. Lohmann und H. Schunck (Hrsg.):
MATHEMATIK - Schlüsseltechnologie für die Zukunft,
Springer Verlag, 1997, 609-624
M. Grötschel, M. Jünger, G. Reinelt: Optimal
Control of Plotting and Drilling Maschines: A Case Study,
Zeitschrift für Operations Research 35 (1991) 61 - 84
Martin Grötschel, Clyde Monma, Mechthild Stoer:
Design of Survivable Networks, in: M. O. Ball
et al. (eds): Network Models (Handb. Oper. Res.
Manage Sci) North-Holland, Amsterdam, 617 - 672 (1995)
Tommy R. Jensen, Bjarne Toft: Graph Coloring Problems,
Wiley, New York, 1995
Andreas Löbel: Optimal Vehicle Scheduling in Public Transit,
Shaker Verlag, 1998
Mechthild Stoer: Design of Survivable Networks
Springer, Berlin, 1992
Mechthild Stoer, Geir Dahl: A polyhedral Approach to multicommodity
survivable network design, Numerische Mathematik 68 (1994) 149 - 167
Doris Tesch: Disposition von Anruf-Sammeltaxis, Deutscher
Universitätsverlag, Wiesbaden 1994
Carsten Thomassen: Five-Coloring Graphs on the Torus,
Journal of Combinatorial Theory B 62 (1994) 11-33
Carsten Thomassen: Color-Critical Graphs on a Fixed Surface,
Journal of Combinatorial Theory B 70 (1997) 67 - 100
Bjarne Toft: Colouring, stable sets and perfect graphs,
in R.l. Graham, M. Grötschel, L. Lovasz (eds.): Handbook of
Combinatorics, Vol 1, Chapter 4, 233 - 288. 1995
D. Wedelin: An algorithm for large scale 0-1 integer programming
with application to airline crew scheduling, Annals of Operations
Research 57, 283-301 (1995)
Eberhard Zehendner: Methoden der Polyedertheorie zur Herleitung von
oberen
Schranken für die Mächtigkeit von Block-Codes, Dissertation,
Mathematisch-
Naturwissenschaftliche Fakultät, Universität Augsburg, July
1986