Fallstudien Diskrete Optimierung (MA4512)

Vorlesung mit integrierter Projektarbeit

Diese Veranstaltung wird durch Studienbeiträge unterstützt.
polytop.png

 

Dozierende: Michael Ritter, Wolfgang Riedl, Paul Stursberg
Umfang: 4 Semesterwochenstunden
ECTS-Bewertung: 5 ECTS

Aktuelles

  • Auf der Konferenz-Website steht der Zeitplan und weitere Informationen zum Abschlussworkshop bereit.
  • Auf http://studium.ma.tum.de/Schulportal/Abitag/WebHome steht das Programm für den Abitag online.
  • Die erste Veranstaltung findet am Dienstag, 17. April 2012, um 10:15 Uhr im Raum 00.09.022 statt. Bitte kommen Sie pünktlich!
  • Eine leicht gekürzte Version der Folien für die Vorbesprechung steht zum Download bereit: vortrag-www.pdf.
  • Die wichtigsten Informationen zu dieser Veranstaltung haben wir auf einem Aushang zusammengestellt: aushang.pdf

Termine

Veranstaltungstermine

Die Veranstaltung findet Dienstags und Freitags, jeweils von 10:15 - 11:45 Uhr, statt. Die genauen Termine finden Sie unten aufgelistet, die Aufstellung wird im Lauf des Semesters aktualisiert. Sie sollten nach Möglichkeit an allen Veranstaltungsterminen teilnehmen. Sollte das einmal nicht möglich sein, sagen Sie bitte (per E-Mail oder persönlich) kurz Bescheid, das hilft uns bei der Planung von Gruppenarbeit und Ähnlichem. Auf jeden Fall sollten Sie zum ersten Veranstaltungstermin am 17.04.2012 anwesend sein, zu diesem Termin lernen Sie Ihr Team kennen und erhalten Ihr Projekt.

Bitte halten Sie sich neben den Vorlesungsterminen den 27.06.20120 (Abitag, Posterpräsentation etwa um die Mittagszeit, genaues Programm auf http://studium.ma.tum.de/Schulportal/Abitag/WebHome) und den 14.07.2012 (Abschlussworkshop) frei. Die Veranstaltung endet mit dem Abschlussworkshop, die Termine in der letzten Juliwoche entfallen also.

Datum Uhrzeit Raum Veranstaltungsinhalt
Do 09.02.2012 16:00 Uhr MI 00.07.011 Vorbesprechung
Di 17.04.2012 10:15 - 11:45 MI 00.09.022 Teameinteilung, Themen, Kennenlernen
Fr 20.04.2012 10:15 - 11:45 Uhr MI 00.09.022 Teampräsentationen, Grundlagen der Projektplanung
Di 24.04.2012 10:15 - 11:45 Uhr MI 00.09.022 Dualität (Wiederholung)
Fr 27.04.2012 10:15 - 11:45 Uhr MI 00.09.022 Vorstellung Projektpläne
Di 01.05.2012 Feiertag
Fr 04.05.2012 10:15 - 11:45 Uhr MI 00.09.022 Dekompositions-Verfahren (Teil 1)
Di 08.05.2012 10:15 - 11:45 Uhr MI 00.09.022 Dekompositions-Verfahren (Teil 2)
Fr 11.05.2012 10:15 - 11:45 Uhr MI 00.09.022 Dekompositions-Verfahren (Teil 3)
Di 15.05.2012 keine Veranstaltung wg. SVV
Fr 18.05.2012 keine Veranstaltung
Di 22.05.2012 10:15 - 11:45 Uhr MI 00.09.022 interne Poster-Präsentation
Fr 25.05.2012 10:15 - 11:45 Uhr MI 00.09.022 Schnittebenenverfahren (Teil 1 - Mixed Integer Cuts)
Di 29.05.2012 Pfingstferien
Fr 01.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Schnittebenenverfahren (Teil 2 - kombinatorische Schnitte)
Di 05.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Branch & Bound (Teil 1 - Branching-Regeln)
Fr 08.06.2012 keine Veranstaltung
Di 12.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Branch & Bound (Teil 2)
Fr 15.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Foliengestaltung & Präsentation
Di 19.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Feedback und Midterm-Presentations (Teil 1: Teams "Strom" und "Routenplanung")
Fr 22.06.2012 10:15 - 11:45 Uhr MI 00.09.022 Midterm-Presentations (Teil 2: Teams "Holztransport" und "Sightseeing") und Evaluation
Di 26.06.2012 10:15 - 11:45 Uhr MI 00.09.022 ILP-Heuristiken
Mi 27.06.2012 ca. 10 - 14 Uhr Magistrale Abitag: Präsentation von Poster und Messestand (s. auch http://studium.ma.tum.de/Schulportal/Abitag/WebHome)
Sa 14.07.2012 9:00 - ca. 19 Uhr HS 0606 (TUM Stammgelände) Abschlussworkshop, weitere Informationen auf der Konferenz-Website.

Im Juli finden außer dem Abschlussworkshop keine festen Termine mehr statt, Sie verwenden die Zeit stattdessen zum eigenständigen Arbeiten, zur Vorbereitung Ihrer Präsentation und für Besprechungen mit Ihren Betreuern.

Material zum Download

  • Anleitung zur Installation und Verwendung von Xpress: xpress-ssh.pdf

Vorbesprechung am 9. Februar 2012

Vorlesung am 17. April 2012

Vorlesung am 20. April 2012

Vorlesung am 24. April 2012

Vorlesung am 4. Mai 2012

Vorlesungen vom 8. und 11. Mai 2012

Vorlesung vom 25. Mai 2012

Vorlesung vom 1. Juni 2012

Galerie und Erläuterungen

Handouts

Vorlesung vom 5. Juni 2012

Vorlesung vom 12. Juni 2012

Vorlesung vom 15. Juni 2012

Vorlesung vom 19. Juni 2012

Vorlesung vom 26. Juni 2012

Inhalte und Methodik

Die Veranstaltung besteht aus zwei eng miteinander verzahnten Teilen: Einem Vorlesungsteil und einem Praxisprojekt. Im Vorlesungsteil werden wichtige Methoden aus der diskreten Optimierung erarbeitet. Sie werden dort Verfahren kennen lernen, die in praktischen Problemstellungen Anwendung finden, und sich mit deren theoretischen Grundlagen, konkreten Anwendungsbeispielen und praktischen Aspekten dieser Verfahren beschäftigen. Von Beginn an arbeiten Sie parallel dazu an einem Praxisprojekt. In kleinen Teams lernen Sie eine Problemstellung aus der Praxis kennen, entwickeln eigenständig geeignete mathematische Modelle, analysieren die entscheidenden strukturellen Eigenschaften der Probleme und wenden Methoden, die Sie in Ihren Vorlesungen und in dieser Veranstaltung kennengelernt haben, auf Ihre Probleme an. Im Lauf des Semesters treten die Praxisprojekte immer stärker in der Vordergrund: Fortschrittsberichte, Diskussionen im Team, mit Ihren Betreuern und im Plenum, Präsentation Ihrer (Zwischen-) Ergebnisse in einer für die Öffentlichkeit geeigneten Form (Poster mit Präsentation) vermitteln Ihnen neben den fachlichen Kenntnissen auch wertvolle Erfahrungen im Projektmanagement, selbstständigem (wissenschaftlichen) Arbeiten und in der Präsentationstechnik. Höhepunkt und Abschluss der Veranstaltung ist ein eintägiger Abschlussworkshop zum Semesterende.

Vorlesung

Inhaltliche Schwerpunkte der Vorlesung sind unter anderem:
  • ganzzahlige Optimierung
  • Anwendungsbeispiele aus der Praxis
  • Modellierung von Optimierungsproblemen
  • Schnittebenenverfahren und ihre Anwendung
  • Branch & Bound-Verfahren, Branch & Cut, Varianten und Spezialisierungen für verschiedene Anwendungsprobleme
  • Approximationsalgorithmen und Heuristiken
  • große ganzzahlige Probleme, Decomposition, Column Generation, Branch & Cut & Price

Praxisprojekt

Der größte Teil der Veranstaltung besteht in der Bearbeitung eines Praxisprojekts in Teams. Schwerpunkte liegen auf Analyse, Modellierung und Umsetzung der gefundenen Lösung und dem Einsatz der in anderen Vorlesungen erlernten Techniken der linearen, ganzzahligen und diskreten Optimierung. Außerdem werden wir die Ergebnisse der Öffentlichkeit und einem wissenschaftlichen Fachpublikum präsentieren. Genaueres zu den Projekten erfahren Sie in der Vorbesprechung. Eine mögliche Auswahl von Themen (ohne Anspruch auf Vollständigkeit, Änderungen sind noch möglich):

Routenplanung mit Wahl der Verkehrsmittel

Die Routenplanung ist eine der klassischen Problemstellungen der kombinatorischen Optimierung. Die Bandbreite von Routenplanungsproblemen reicht von Kürzeste Wege-Problemen (wie sie etwa beim Auto-Navigationsgerät gelöst werden) über das Traveling Salesman Problem (das zahlreichen Anwendungen besitzt, beispielsweise im Design von Halbleiterschaltungen) bis hin zu Routing-Problemen in Computernetzen, bei denen Kriterien wie Ausfallsicherheit oder geringe Latenz eine wichtige Rolle spielen. In diesem Projekt werden Sie sich vor allem mit der "klassischen" Variante auseinandersetzen, einen Weg oder eine Rundtour zu vorgegebenen Orten zu finden. Betrachtet man solche Probleme im städtischen Umfeld, so stehen meist eine Vielzahl von Verkehrsmitteln zur Verfügung, die sich für die Fahrt nutzen lassen: Neben einer Auto- bzw. Taxifahrt kommen auch öffentliche Verkehrsmittel wie U-Bahn oder Bus für die Beförderung in Frage, und natürlich kann man die Strecke oder Teile davon auch zu Fuß zurücklegen. Diese Wahlmöglichkeit wird aber durch die Verfügbarkeit öffentlicher Verkehrsmittel und deren Fahrpläne eingeschränkt - selbst eine schnelle U-Bahn-Verbindung kann unattraktiv sein, wenn man zur gewünschten Abfahrtszeit noch 20 Minuten auf die nächste U-Bahn warten müsste. Im Rahmen des Projekts werden Sie untersuchen, wie sich Routenplanungsprobleme modellieren und lösen lassen, bei denen eine freie Wahl zwischen mehreren alternativen Verkehrsmitteln besteht (und zwar so, dass sich das Verkehrsmittel auch unterwegs wechseln lässt), bei denen manche durch Fahrpläne eingeschränkt sein können.

Sightseeing

Sie verbringen ein Wochenende in einer fremden Stadt und möchten in der verfügbaren Zeit möglichst viele der zahlreichen Sehenswürdigkeiten besuchen können, die diese Stadt zu bieten hat. Natürlich haben Sie Ihre eigenen Vorstellungen davon, welche Attraktionen besonders interessant sind - vielleicht begeistern Sie sich für Architektur, vielleicht sind Sie ein Kunstfan, vielleicht wollen Sie die gastronomischen Höhepunkte Ihres Urlaubsziels kennenlernen? Leider haben Sie nicht nur zuwenig Zeit, sondern auch zuwenig Geld um sich all die spannenden Dinge anzusehen, die diese Stadt zu bieten hat. In diesem Projekt beschäftigen Sie sich mit der Frage, wie Sie eine optimale Auswahl aus den verfügbaren Sehenswürdigkeiten treffen und wie die dazu passende Besuchsroute aussieht, um das Beste aus Ihrem Urlaub und Ihrem bescheidenen Budget zu machen. Das Sightseeing-Problem ist teilweise mit dem Projekt "Routenplanung mit Wahl der Verkehrsmittel" verwandt, weil Sie in den meisten Städten natürlich auch mehrere Verkehrmittel zur Wahl haben, setzt aber einen etwas anderen Schwerpunkt.

Transportprobleme in der Holzindustrie

In der Holzverarbeitung gibt es traditionell zwei voneinander getrennte Transportkreisläufe: Zuerst werden die gefällten Bäume vom Forst in ein Sägewerk transportiert, dann werden die gesägten Bretter aus dem Sägewerk in einen holzverarbeitenden Betrieb gebracht. Weiterentwicklungen in der Transporttechnik machen es nun aber möglich, für beide Kreisläufe ein einheitliches LKW-Modell zu nutzen, indem sowohl Stämme als auch Bretter in Container geladen werden. Das bringt außerdem den Vorteil mit sich, das Be- und Entladen der Container bereits durchgeführt werden können, bevor der LKW selbst vor Ort ist. Durch diese Innovation erhöht sich allerdings die Komplexität des Problems deutlich: Derselbe LKW kann jetzt für beide Arten von Transport eingesetzt werden, außerdem muss dafür gesorgt werden, dass leere Container zur Beladung rechtzeitig dort eintreffen, wo sie gebraucht werden. Der Preis für die einheitliche Betrachtung des Transportnetzwerks ist also, dass ein zusätzliches Transportproblem gelöst und mit den beiden anderen Transportströmen koordiniert werden muss, nämlich das der Container. Darüber hinaus sind zahlreiche Nebenbedingungen wie Lade-/Entladezeiten oder arbeitsrechtliche Anforderungen zu beachten. Aufbauend auf den Ergebnissen eines Projekts aus dem Vorjahr entwickeln Sie in diesem Projekt vorhandene Modelle weiter, untersuchen alternative algorithmische Ansätze und implementieren Ihre Ergebnisse.

Ausbauplanung für Stromnetze

Der zunehmende Ausbau regenerativer Energien und die Energiewende stellen die Netzinfrastruktur in Deutschland vor neue Herausforderungen. Zum einen verschiebt sich die Erzeugungsleistung von Strom zunehmend in windreiche Gegenden (Nord-/Ostdeutschland), zum anderen kommt der Stromspeicherung (die vorwiegend in Süddeutschland möglich ist) auch eine immer größere Bedeutung zu, um Lastspitzen besser ausgleichen zu können. Auf der anderen Seite verstärkt sich in letzter Zeit der Trend zur dezentralen Energieversorgung - Windkraftwerke, Solaranlagen, Biomassekraftwerke und ähnliche Kleinkraftwerke werden an zahlreichen Standorten errichtet. Sowohl auf regionaler wie auch auf nationaler Ebene kommt dem Versorgungsnetz daher eine hohe Bedeutung zu und Experten diskutieren seit einiger Zeit über mögliche Netzengpässe und den notwendigen Ausbau der Stromnetze. In diesem Projekt beschäftigen Sie sich mit den technischen Gegebenheiten des Stromnetzes, lernen verschiedene Modelle für Stromnetze, Kraftwerkseinsatz und die Integration regenerativer Energien kennen und entwickeln auf dieser Grundlage ein eigenes Ausbaumodell, mit dem Sie Engstellen identifizieren und Wege zu einem wirtschaftlich optimalen Netzausbau aufzeigen können.

Konstruktion von Getrieben

In der Mechanik spielen Getriebe in fast jedem Einsatzbereich eine wichtige Rolle. Schalt- und Automatikgetriebe im PkW, Getriebe für Windkraftanlagen oder innovative Getriebekonzepte für Hybridfahrzeuge zeigen nur einen kleinen Ausschnitt der zahlreichen Einsatzmöglichkeiten. Für die Entwicklung dieser hochkomplexen technischen Meisterwerke sind in ein hohes Maß an Erfahrung und auch viele Versuche notwendig. Ein Ansatz in der Entwicklung neuer Getriebe ist die Abbildung der wichtigen Eigenschaften eines Getriebes in einem Graphen. Basierend auf einem geeigneten Modell entwickelt man dann Ansätze, möglichst gute Graphenstrukturen zu erzeugen und diese wiederum in Getriebe "zurückzuübersetzen". In diesem Projekt beschäftigen Sie sich mit der Umsetzung der zentralen technischen Eigenschaften eines Getriebes in ein Graphenmodell und mit der Synthese eines optimalen Graphen (und damit eines optimalen Getriebes) zu vorgegebenen Eigenschaften Anforderungen wie Übersetzungsverhältnis oder Leistungsübertragung.

Methodik

  • Teamarbeit in Eigenverantwortung
  • Vorlesungsteile
  • praxisnahes Arbeiten
  • Präsentation und Fortschrittsberichte
  • Darstellung der Probleme und Ansätze als Poster für eine größere Öffentlichkeit
  • Abschlussworkshop

Was haben Sie davon?

  • 5 ECTS für die Master-Studiengänge in Mathematik
  • Erfahrung in der praktischen Umsetzung Ihrer theoretischen Kenntnisse
  • Softskills: Teamarbeit, Aufbereitung und Vermittlung von Ergebnissen, eigenständiges Arbeiten
  • möglicher Einstieg in eine Abschluss- oder Projektarbeit am Lehrstuhl

Was sollten Sie mitbringen?

  • Kenntnisse in linearer Optimierung (z.B. aus der Vorlesung "Lineare Optimierung")
  • von Vorteil: Kenntnisse in diskreter Optimierung (z.B. aus "Discrete Optimization", "Combinatorial Optimization") - wenn Sie sich nicht sicher sind, ob Ihre Vorkenntnisse ausreichen, sprechen Sie uns einfach an.
  • Spaß an praxisnahen Problemstellungen
  • Engagement
  • von Vorteil: Programmierkenntnisse (die vorherige Teilnahme an einem Computerpraktikum ist dazu empfehlenswert!)