You are here: SS2011 > CaseStudies (13 Sep 2011, MelanieBestle?)

 

 
Fallstudien Diskrete Optimierung, MA4512

Vorlesung mit integrierter Projektarbeit

Diese Veranstaltung wird durch Studienbeiträge unterstützt.Studienbeitraege Banner

 

Dozierende: Michael Ritter, Melanie Bestle
Umfang: 4 Semesterwochenstunden
ECTS-Bewertung: 5 ECTS

Aktuelles

  • 19.7.2011: Die Daten für den Abschlussworkshop sind jetzt auf der Conference Website zu finden.
  • 12.05.2011: Ab kommenden Dienstag, den 17.05.2011, findet die Vorlesung am Dienstag jeweils von 10:40 - 12:10 Uhr statt.

Termine

Veranstaltungstermine (voraussichtlich)

Bitte halten Sie sich neben den Vorlesungsterminen den 08.06.2011 (Abitag, Posterpräsentation) und den 23.07.2011 (Abschlussworkshop) frei. Die Veranstaltung endet mit dem Abschlussworkshop, die Termine in der letzten Juliwoche entfallen also.

Datum Uhrzeit Raum Veranstaltungsinhalt
Di 03.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Organisatorisches, Teameinteilung, Kennenlernen
Fr 06.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Teampräsentationen, Grundlagen der Projektplanung
Di 10.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Wiederholung: Dualität
Fr 13.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Präsentation der Projektpläne
Di 17.05.2011 10:40 - 12:10 Uhr MI 00.09.022 Branch & Bound 1
Fr 20.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Branch & Bound 2
Di 24.05.2011 10:40 - 12:10 Uhr MI 00.09.022 Symmetrie, Orbital Branching, Grundlagen TSP/VRP
Fr 27.05.2011 10:15 - 11:45 Uhr MI 00.09.022 Schnittebenenverfahren am Beispiel von TSP/VRP
Di 31.05.2011 08:30 - 10:00 Uhr MI 00.09.022 interne Posterpräsentation, Vorstellung Messestände (Terminverschiebung wg. SVV)
Fr 03.06.2011 10:15 - 11:45 Uhr MI 00.09.022 keine Vorlesung
Di 07.06.2011 10:40 - 12:10 Uhr MI 00.09.022 ILP-Heuristiken
Mi 08.06.2011 11:45 - 14:00 Uhr MI Magistrale Posterausstellung und Messestände zum Abitag
Fr 10.06.2011 10:15 - 11:45 Uhr MI 00.09.022 Column Generation
Di 14.06.2011 Pfingstferien
Fr 17.06.2011 10:15 - 11:45 Uhr MI 00.09.022 Decomposition-Verfahren 1
Di 21.06.2011 10:40 - 12:10 Uhr MI 00.09.022 Decomposition-Verfahren 2
Fr 24.06.2011 10:15 - 11:45 Uhr MI 00.09.022 keine Vorlesung
Di 28.06.2011 10:40 - 12:10 Uhr MI 00.09.022 Tipps zur Foliengestaltung und zur freien Rede
Fr 01.07.2011 10:15 - 11:45 Uhr MI 00.09.022 interne Präsentation: Fortschrittsberichte mit Feedback (Teil 1, Teams "Instandsetzung" und "Healthcare")
Di 05.07.2011 10:40 - 12:10 Uhr MI 00.09.022 interne Präsentation: Fortschrittsberichte mit Feedback (Teil 2, Teams "Holztransport", "Sightseeing" und "Strom")
Fr 08.07.2011 10:15 - 11:45 Uhr MI 00.09.022 vsl. keine gemeinsame Veranstaltung
Di 12.07.2011 10:40 - 12:10 Uhr MI 00.09.022 keine gemeinsame Veranstaltung
Fr 15.07.2011 10:15 - 11:45 Uhr MI 00.09.022 keine gemeinsame Veranstaltung
Di 19.07.2011 10:40 - 12:10 Uhr MI 00.09.022 keine gemeinsame Veranstaltung
Fr 22.07.2011 10:15 - 11:45 Uhr MI 00.09.022 keine gemeinsame Veranstaltung
Sa 23.07.2011 ganztägig Stammgelände Abschlussworkshop

Material zum Download

  • xpress-ssh.pdf: Anleitung zum Zugriff auf den Xpress-Lizenzserver (Stand: 16. Mai 2011)
  • SVN-aufsetzen.pdf: Anleitung zum Einrichten eines SVN-Repositories in der Informatikhalle (Stand: 16. Mai 2011)

Dienstag, 3. Mai 2011

  • zeitstrahl.pdf: Zeitplan im Überblick mit den wichtigsten Terminen (Stand: 16. Mai 2011)

Freitag, 6. Mai 2011

Dienstag, 10. Mai 2011

Dienstag, 17. Mai 2011

Freitag, 20. Mai 2011

Dienstag, 24. Mai 2011

Freitag, 27. Mai 2011

Dienstag, 07. Juni 2011

Freitag, 10. Juni 2011

Freitag, 17. Juni 2011

Dienstag, 21. Juni 2011

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):
  • erneuerbare Energien: optimaler Einsatz von Speicherkraftwerken unter Einbeziehung des Stromnetzes
  • Sightseeing-Probleme: Planung einer Stadtbesichtigung mit verschiedenen Verkehrsmitteln
  • Tourenplanung für mobile Krankenpflegedienste
  • Gütertransport mit speziellen Containern
  • optimale Planung von Straßenbauarbeiten

Sightseeing-Probleme

Für eine Stadtbesichtigung (oder jede touristische Rundfahrt) gibt es vor allem zwei limitierende Faktoren: Die meisten Besucher haben nur beschränkte Zeit und außerdem ein gewisses Budget zur Verfügung. Die zentrale Frage für eine gelungene Städtereise ist dann: Welche Sehenswürdigkeiten wählt man im Rahmen der verfügbaren Zeit und des vorhandenen Budgets aus, um möglichst viele interessante Einblicke zu bekommen? Natürlich gibt es verschiedene Vorlieben - manche Touristen bewundern gerne die Kunstschätze in den Museen, andere sind an Naturschönheiten und Parks interessiert, wieder andere zieht es an die geschichtsträchtigen Orte einer Stadt. In größeren Städten kommt dazu noch die Wahl des Beförderungsmittels: Ein Spaziergang macht es zwar einfach, viele Eindrücke einzufangen, dafür ist man aber sehr langsam unterwegs. Schneller, aber auch deutlich kostspieliger, wäre eine Fahrt mit dem Taxi. Öffentliche Verkehrsmittel wie U-Bahnen überbrücken größere Entfernungen ebenfalls schnell und sind kostengünstiger, dafür aber weniger flexibel. Interesse, Budget und Zeit "unter einen Hut" zu bekommen, ist Aufgabe des Sightseeing-Problems, mit dem Sie sich in diesem Projekt beschäftigen werden.

erneuerbare Energien

Elektrische Energie wird zunehmend aus regenerierbaren Quellen gewonnen, von großer Bedeutung in Deutschland ist etwa die Windenergie. Diese Art der Energieerzeugung ist allerdings nur bedingt planbar, die Speicherung von Energie gewinnt daher eine immer größere Bedeutung. Da Stromerzeugung, Speicherung und Verbrauch häufig nicht am selben Ort stattfinden, spielt außerdem die Frage des Stromtransports eine wichtige Rolle, der Ausbau der Stromnetze ist von der Bundesregierung zu einem wichtigen energiepolitischen Ziel erklärt worden. In diesem Projekt beschäftigen Sie sich mit der Frage, wie Speicherkraftwerke unter Berücksichtigung aller relevanten Parameter und vor allem des vorhandenen Netzes aktuell optimal genutzt werden können. In einem weiteren Schritt werden Sie dann identifizieren, wo der Ausbaubedarf aktuell am größten ist und welche Anforderungen an Stromspeicher wie an die Netzinfrastruktur der Zukunft gestellt werden sollten.

Einsatzplanung für mobile Pflegedienste

Mobile Pflegedienste geben älteren und hilfebedürftigen Menschen die Unterstützung, die sie benötigen, um trotz gewisser Einschränkungen ein selbstbestimmtes Leben in gewohnter Umgebung führen zu können. Die Hilfen reichen dabei von Unterstützung beim Einkauf bis hin zur Betreuung schwer pflegebedürftiger Menschen, entsprechend variabel sind auch die Anforderungen an das Pflegepersonal. Um sowohl Pflegepersonal als auch den betreuten Personen einen sicheren Rahmen zu geben, sind bei der Einsatzplanung für die Pflegedienste eine ganze Reihe von Bedingungen zu beachten. So sollen die betreuten Personen je nach Schwere ihrer Hilfsbedürftigkeit beispielsweise immer von derselben Pflegekraft betreut werden, die erforderlichen fachlichen Kenntnisse müssen vorhanden sein, die nötige Zeit kann stark variieren, Arbeitszeitrestriktionen sind einzuhalten und die Zeit für die Fahrt zu den Patienten muss ausreichend bemessen sein. In diesem Projekt beschäftigen Sie sich mit der Frage, wie unter all diesen Restriktionen eine optimale Einsatzplanung für den Pflegedienst durchgeführt werden kann. Eventuell betrachten Sie dazu eine besondere Herausforderung im städtischen Umfeld: Dort stehen als Alternative zum Einsatz eines PKW möglicherweise auch öffentliche Verkehrsmittel zur Verfügung, die gerade zu Stoßzeiten häufig zuverlässiger, schneller und kostengünstiger sind und die Parkplatzsuche überflüssig machen, dafür aber zusätzliche Planungsarbeit erfordern.

Transporte mit Spezialcontainern

Seit einiger Zeit werden in verschiedenen Bereichen der Transportwirtschaft sogenannte "Faltcontainer" eingesetzt. Der Vorteil dieser Container besteht darin, dass sie im leeren Zustand zusammengelegt werden können und sich auf diese Weise mehrere Container auf ein Transportfahrzeug verladen lassen. In diesem Projekt werden Sie sich mit der Frage beschäftigen, wie die so entstehenden neuen Potentiale optimal genutzt werden können. Sie bearbeiten das Problem dabei am Beispiel einer Fragestellung aus der Forstwirtschaft.

Planung von Instandsetzungsarbeiten

Straßen, Brückenbauwerke und Tunnels müssen regelmäßig gewartet werden, um in verkehrssicherem Zustand zu bleiben. Dafür ist es erforderlich, das betroffene Bauwerk ganz oder teilweise für den Verkehr zu sperren. In diesem Projekt gehen Sie der Frage nach, welche Bauwerke man zu welchen Zeitpunkten warten sollte, um die negativen Einflüsse auf den Verkehr so gering wie möglich zu halten. Daneben sind natürlich weitere Einschränkungen wie das verfügbare finanzielle Budget oder das vorhandene Personal zu beachten. Die besondere Schwierigkeit liegt aber darin, dass sich die Effekte einer Sperrung erst bei Betrachtung des gesamten Verkehrsnetzes erschließen, durch das auch komplizierte Abhängigkeiten zwischen Bauwerken entstehen können.

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!)

Topic revision: r57 - 13 Sep 2011 - 08:20:26 - MelanieBestle?
 
Bottomleft LogoBottomright Logo
Impressum  |  Disclaimer und Rechtshinweise  |  AnregungenCopyright Technische Universität München, M9