Projekt-Seminar: Diskrete Optimierung (WS 09/10)

	Projekt-Seminar: Diskrete Optimierung
	Wintersemester 2009/2010

LV-Nr.: 3236 L365

Dr. Ralf Borndörfer (www)

und Dr. Armin Fügenschuh (www)

und Prof. Dr. Martin Grötschel (www)

und Benjamin Hiller (www)

und Elmar Swarat (www)

Aktuell Inhalt Voraussetzungen Seminardurchführung Termine Programm Themen Hinweise zu Präsentationen Kontakt

Im Wintersemester 2009/2010 bieten wir an der TU Berlin ein Projektseminar an, bei dem Studierende lernen sollen, reale Praxisprobleme aus den Bereichen Telekommunikation, öffentlicher Personenverkehr, Logistik oder Gastransport zu lösen.

Aktuell

5. Treffen: 19. April 2010, 16-18 Uhr, Raum MA 313

Auf der Download-Seite von SCIP gibt es 32- und 64-Bit Binaries von SCIP inklusive zimpl-Reader zum Download, unter Binaries den 6. und 7. Link

Inhalt

Ziel des Seminars ist (neben der Beschäftigung mit interessanten mathematischen Themen und spannenden Anwendungen) die Vorbereitung auf die Berufswelt nach dem Studium.

Voraussetzungen

Mathematische Kenntnisse: Erfolgreicher Besuch der Vorlesung „Graphen- und Netzwerkalgorithmen (ADM I)“, möglichst Besuch der Vorlesung „Linear and Integer Programming (ADM II)“ (kann parallel im WS 09/10 erfolgen).
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. Die Aufgabe ist -- wie in der Praxis üblich -- "weich" formuliert. Die Gruppe muss versuchen, daraus (mindestens) ein mathematisches Modell zu formulieren, mit dessen Hilfe das Praxisproblem vermutlich gelöst werden kann. In Interaktion mit den Seminarleitern wird dieses Modell verbessert oder korrigiert, bis eine mathematische Fragestellung entstanden ist, die die Praxisanforderungen angemessen abbildet. Danach muss die Gruppe ein Fallbeispiel mit Daten aus der Praxis lösen. Hierzu muss die Gruppe, je nach vorliegender Aufgabe, eigene Heuristiken entwickeln und implementieren oder mit (den Seminarteilnehmern bereitgestellter) Optimierungssoftware (Zimpl, Soplex, SCIP) Lösungsexperimene mit hoffentlich positivem Ausgang unternehmen. Die erzielten Ergebnisse sollen in einer Ausarbeitung von 5 - 10 Seiten (mit guter gestalterischer Qualität) zusammengefasst und in einer Präsentation am Ende des Semesters (möglichst professionell) vorgestellt werden.

Termine

Anmeldungen waren per E-Mail (an fuegenschuh@zib.de) möglich. Da sich bis zum 10. Oktober 2009 mehr als 9 Teilnehmer angemeldet hatten (das war eine Voraussetzung für die Durchführung des Seminars in Gruppen), fand die erste Sitzung mit der Bildung von Gruppen, der Vergabe von Themen und der Besprechung des Zeitplans am 19. Oktober 2009 in der TU Berlin statt.
Ein 2. Treffen gab es am 14. November 2009.
Das 3. Treffen fand statt am Mo. 21. Dezember, 14 Uhr s.t., Raum MA 313.
Ein 4. Treffen erfolgte am 8. Februar 2010, 14-16 Uhr, Raum MA 313.
Das 5.Treffen ist geplant für den 19. April 2010, 16-18 Uhr, Raum MA 313.

Programm

1. Meilenstein 14.11.2009, bis dahin thematische Einarbeitung, Literatur und erste Modellansätze
2. Meilenstein 21.12.2009, bis dahin Ausarbeitung der Modelle, erste Implementierungen
Endpräsentation 08.02.2010, Modellvorstellung, Auswertung und Präsentation der Ergebnisse

Themen

Optimierung von Gasnetzwerken
Planung der Mautkontrolldienste

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
Dr. Ralf Borndörfer	n.V.	ZIB	84185-243	borndoerferzib.de
Dr. Armin Fügenschuh	n.V.	ZIB	84185-205	fuegenschuhzib.de
Prof. Dr. Martin Grötschel	n.V.	ZIB TU /MA 302	84185-210 314-23266	groetschelzib.de
Benjamin Hiller	n.V.	ZIB	84185-406	hillerzib.de
Elmar Swarat	n.V.	ZIB	84185-244	swaratzib.de

Zuletzt aktualisiert: 10. März 2010