Projekt-Seminar: Diskrete Optimierung (SS 2010)

	Projekt-Seminar: Diskrete Optimierung
	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 Inhalt Voraussetzungen Seminardurchführung Aufgabenbeschreibung Termine Programm Themen Daten Hinweise zu Präsentationen Kontakt

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

Zu folgenden Treffen soll jede Gruppe den Projektstatus präsentieren:

am 10.05.2010 um 13:30 Uhr
am 11.06.2010 um 14:00 Uhr
am 08.07.2010 um 14:00 Uhr

jeweils im Raum MA 313. Weiter unten finden Sie Aufgabenblätter sowie erste Daten zu beiden Themen.

Inhalt

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

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

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

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

flexible Zugwünsche

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

Die erste Sitzung mit der Bildung von Gruppen, der Vergabe der Aufgaben und der Besprechung des Zeitplans fand am
13. April 2010 in der TU Berlin statt.
Die weiteren Termine sind unter dem Punkt Aktuell zu finden.

Programm

1. Meilenstein: Thematische Einarbeitung, Literatur und erste Modellansätze (10.05.2010)
2. Meilenstein: Ausarbeitung der Modelle, erste Implementierungen (11.06.2010)
3. Meilenstein: Modellvorstellung, Auswertung und Präsentation der Ergebnisse (08.07.2010)

Themen

Daten

Train Timetabling (Hier werden künftig Daten zu diesem Projekt zur Verfügung gestellt)
FTTB-Planung (Hier werden künftig Daten zu diesem Projekt zur Verfügung gestellt.)

Hinweise zu den Präsentationen und Ausarbeitungen

Richtlinien für die Vortragsgestaltung und die Ausarbeitung:

Ein wesentlicher Teil ist eine Präsentation von ca. einer Stunde über das zugeteilte Projekt. Die Ausgangssituation, das mathematische Modell, die Lösungsmethodik und die Ergebnisse sollen in verständlicher Form vorgestellt werden. Der Vortrag soll eine ansprechende äußere Form haben.
Vortragsform und Vortragsmedien können frei gewählt werden. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Insbesondere bei Beamerbenutzung sollte die Technik vorher geprüft werden.
Zum Vortragstermin ist von den Vortragenden eine etwa 5-10-seitige Ausarbeitung zum Thema vorzulegen. Diese wird von der jeweiligen Projektgruppe selbst vervielfältigt und an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen die wesentlichen Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in ``Publikationsqualität'' vorliegen. Dazu gehört insbesondere am Anfang ein Kopf mit Angabe von Titel, Autor, Veranstaltung und wesentlichen Quellen und am Ende ein Quellen- und Literaturverzeichnis (das im Umfang von 5 Seiten eingeschlossen ist). Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley. Bitte achten Sie darauf, dass es sich um eine ``aktuelle'' Version handelt, die LaTeX2e behandelt.)

Bei der Literatursuche sind folgende Links nützlich:

Mathematische Artikel: Zentralblatt
Mathematische Webseiten: MathSearch
Mathematische und Informatik-Abstracts/Bibliographie: CiteSeer
Informatikartikel/Bibliographie: ACM Portal
Wissenschaftliches Googlen: GoogleScholar

Kontakt

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

Zuletzt aktualisiert: 16. April 2010