Zur TUB

Projekt-Seminar: Diskrete Optimierung

Zur Seite des Instituts für Mathematik
 

Sommersemester 2010

 
LV-Nr.: 3236 L 365

 
Prof. Dr. Martin Grötschel (www) und    Dr. Ralf Borndörfer (www)   und   Dr. Armin Fügenschuh (www)   und   Dr. Axel Werner (www) und    Christian Raack (www)   und   Thomas Schlechte (www)
 

Aktuell (down)   Inhalt (down)   Voraussetzungen (down)   Seminardurchführung (down)   Aufgabenbeschreibung (down)   Termine (down)   Programm (down)   Themen (down)   Daten (down)   Hinweise zu Präsentationen (down)   Kontakt (down)


Im Sommersemester 2010 bieten wir an der TU Berlin wiederum ein Projektseminar an, bei dem Studierende lernen sollen, reale Anwendungen aus der Praxis zu lösen. Wir konzentrieren uns diesmal auf zwei Praxisthemen (siehe Inhalt).

Presentations during the semester and the final report can be made in German or English. Supervision in English language is offered as well.

Aktuell (up)

Zu folgenden Treffen soll jede Gruppe den Projektstatus präsentieren: jeweils im Raum MA 313. Weiter unten finden Sie Aufgabenblätter sowie erste Daten zu beiden Themen.

Inhalt (up)

Ziel des Seminars ist (neben der Beschäftigung mit interessanten mathematischen Themen und spannenden Anwendungen) die Vorbereitung auf die Berufswelt nach dem Studium. Es werden zwei große Themenkomplexe betrachtet:
1. Train Timetabling
2. FTTB-Planung

Voraussetzungen (up)

Mathematische Kenntnisse: Erfolgreicher Besuch der Vorlesung „Graphen- und Netzwerkalgorithmen (ADM I)“, möglichst Besuch der Vorlesung „Linear and Integer Programming (ADM II)“.
Programmierung: Bereitschaft, Umgang mit Modellierungssprachen (wie Zimpl) und Optimierungssoftware (wie SCIP) zu erlernen. Programmierkenntnisse (in einer beliebigen Programmiersprache) sind erwünscht.
Präsentationssoftware und Textverarbeitung: Die Präsentation soll mit professionellen Werkzeugen (wie Powerpoint, LaTeX-Beamer, Keynote, pdf, o.ä.) erfolgen, Vorkenntnisse in mathematischer Textverarbeitung (LaTeX, Word/Formeleditor, o.ä.) werden ebenfalls erwartet. Der „Feinschliff“ erfolgt im Seminar.

Seminardurchführung (up)

Beim ersten Treffen (siehe unten) werden die Teilnehmer in Gruppen von 3 - 4 Personen aufgeteilt. Jede Gruppe erhält eine Aufgabe, die aus einem am ZIB durchgeführten Industrieprojekt stammt (siehe Beschreibung unten). Die Aufgabe ist -- wie in der Praxis üblich -- "weich" formuliert. Die Gruppe soll daraus ein mathematisches Modell formulieren, mit dessen Hilfe das Praxisproblem für kleine Instanzen gelöst werden kann. In regelmäßiger Interaktion mit den Seminarleitern (gedacht ist an zweiwöchige Teffen am ZIB) wird dieses Modell verbessert oder korrigiert, bis eine mathematische Fragestellung entstanden ist, die die Praxisanforderungen angemessen abbildet. Danach muss die Gruppe ein Fallbeispiel mit umfangreicheren Daten aus der Praxis lösen. Hierzu müssen die Teilnehmer, je nach vorliegender Aufgabe, Literaturstudien betreiben, eigene Heuristiken entwickeln und implementieren oder mit (bereitgestellter) Optimierungssoftware (Zimpl, Soplex, SCIP) Lösungsversuche mit hoffentlich positivem Ausgang unternehmen. Die erzielten Ergebnisse sollen in einer Ausarbeitung von 5 - 10 Seiten (mit guter gestalterischer Qualität) zusammengefasst und in drei bis vier semesterbegleitenden Präsentationen möglichst professionell vorgestellt werden.

Das erste dieser Treffen findet 3 - 4 Wochen nach Themenvergabe statt. Hierbei sollen die Teilnehmer ihre Modellierungsansätze, erste Testrechnungen und Literaturstudien vorstellen. Ferner ist ein Projektplan mit Kostenkalkulation und Meilensteinplanung aufzustellen, der auch die Aufgaben innerhalb der Gruppe regelt.

Aufgabenbeschreibung (up)

Projekt: Train Timetabling
Verantwortlich: Ralf Borndörfer, Armin Fügenschuh, Thomas Schlechte.

graph
flexible Zugwünsche
schedule
Fahrplanlösung

Ein Thema des Projektseminars wird "Train Timetabling" sein.
Die Studentengruppe (3-4 Studenten) erhält mehrere Instanzen bzgl. eines kleinen Testnetzes mit Knoten und Kanten sowie Fahrzeiten und weitere zugehörige Daten (in XML, visualisierbar mit TraVis, siehe http://ttplib.zib.de) Ferner erhalten Sie eine anwendungsbezogene Fragestellung, z.B. die Anzahl konfliktfreier Güterzüge im Netz zu maximieren unter Berücksichtigung des gegebenen Personenverkehrs. Es wird jedoch kein fertig ausformuliertes mathematisches Modell mitgeliefert. Erster Arbeitsauftrag der Gruppe wird es sein nach der Literaturrecherche, ein geeignetes MILP-Modell aufzustellen. Nach ca. 3 Wochen sollten die Serminarteilnehmer, ggfs. mit unserer Hilfestellung, so weit sein, ein lauffähiges Modell implementiert (z.B. mittels Zimpl) zu haben und dieses auch lösen zu können (SCIP, CPLEX, oder GuRoBi). Sie werden erleben, dass die Testinstanz zwar rechenbar ist, die Laufzeit aufgrund der schieren Größe des Modells aber sehr hoch ist (etwa 1 Tag bis zur globalen Optimalität). Im nächsten Schritt bekommt die Gruppe eine größere Testinstanz, welche der Löser dann nicht mehr rechnen kann. Ab hier ist die mathematische Kreativität der Teilnehmer gefordert, um auch für solche Szenarien in annehmbarer Zeit möglichst beweisbar gute Lösungen zu finden. Dabei sind sowohl der Einsatz von Konstruktions-Heuristiken, die das Problem versuchen, aus dem Stand zu lösen, als auch Netzaggregationen oder spezielle Problemdekompositionen, erwünscht.

Projekt: FTTB-Planung
Verantwortlich: Axel Werner, Christian Raack

graph


Thema des Projekts ist die Planung von optischen Zugangsnetzen in der Telekommunikation. FTTB steht hierbei für "fibre to the building" und verdeutlicht die Strategie, die bisherigen Kupferleitungen für den DSL-Betrieb in Zugangsnetzen gegen Glasfasertechnik auszutauschen. Hocheffiziente optische Datenübertragung soll Bandbreiten für Haushalte auch jenseits von 100 Mbit/s ermöglichen. Das Austauschen der Kabelinfrastruktur auf der sogenannten "letzten Meile" zum Kunden ist enorm kostenintensiv und aufwendig, da zum Teil komplette Straßenzüge aufgegraben werden müssen. Aufgabe in diesem Projekt ist es, ein solches Glasfasernet (oder zumindest Teile davon) möglichst kostengünstig zu planen. Dazu soll die Gruppe mathematische Modelle entwickeln, die sowohl technische als auch planerische Vorgaben berücksichtigen. Diese Modelle sollen implementiert werden, um damit verschiedene Fragestellungen zu untersuchen. Als Testinstanzen werden Straßennetze und Parameter verschiedener Ausbaugebiete zur Verfügung gestellt. Die Studenten sollen mit selbst entwickelten Ansätzen optimierte Netze berechnen und diese visualisieren. Ähnlich wie im Projekt "Train Timetabling" sollen die Ansätze zunächst an einem relativ kleinen Beispiel entwickelt werden. Um danach auch größere Instanzen in den Griff zu bekommen, sollen die Methoden dann verbessert werden und gegebenenfalls durch Heuristiken, Dekompositionsansätze und ähnliche Techniken ergänzt werden.


Termine (up)


Programm (up)


Themen (up)


Daten (up)

Hinweise zu den Präsentationen und Ausarbeitungen (up)

Richtlinien für die Vortragsgestaltung und die Ausarbeitung: Bei der Literatursuche sind folgende Links nützlich:

Kontakt (up)


 
Sprechstunde
Raum Telefon Email
Groetschel
Prof. Dr. Martin Grötschel (www) n.V. ZIB
TU /MA 302
84185-210
314-23266
groetschelzib.de
Borndörfer
Dr. Ralf Borndörfer (www) n.V. ZIB 84185-243 borndoerferzib.de
Fügenschuh
Dr. Armin Fügenschuh (www) n.V. ZIB 84185-205 fuegenschuhzib.de
Werner
Dr. Axel Werner (www) n.V. ZIB 84185-356 wernerzib.de
Raack
Christian Raack (www) n.V. ZIB 84185-369 raackzib.de
Schlechte
Thomas Schlechte (www) n.V. ZIB 84185-317 schlechtezib.de

Zuletzt aktualisiert: 16. April 2010