You are here: SS2009 > FelixKlein (07 Feb 2011, MichaelRitter)

 

 
Diskrete Optimierung:
Fallstudien aus der Praxis

Vorlesung mit integriertem Projektseminar

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

 

Dozierende: Dr. Barbara Langfeld, Dr. Michael Ritter, Barbara Wilhelm
Umfang: 4 Semesterwochenstunden

Aktuelles

Ergebnisse der Projektgruppen

Termine

Veranstaltungstermine

Die erste Vorlesung findet statt am Montag, 20. April 2009, 14:00 - 15:30 in Raum MI 00.10.011. Weitere Termine:
Tag Uhrzeit Raum
Montags 14:00 - 15:30 Uhr MI 00.10.011
Donnerstags 14:15 - 15:45 MI 00.10.011

Ausweichtermine

Wegen diverser Feiertage müssen wir mehrere Ausweichtermine festlegen:
ursprünglicher Termin Ausweichtermin
Donnerstag, 21. Mai 2009 (Christi Himmelfahrt) Mittwoch, 20. Mai 2009, von 12:10 bis 13:40 Uhr (Raum MW 1701!)
Montag, 1. Juni 2009 (Pfingsten) Mittwoch, 3. Juni 2009, von 12:10 bis 13:40 Uhr
Donnerstag, 11. Juni 2009 (Fronleichnam) Mittwoch, 10. Juni 2009, von 15:45 bis 17:15 Uhr

Besondere Termine

Tag Uhrzeit Raum Veranstaltung
Samstag, 25. Juli 2009 14:45 HS 0606 Gastvortrag von Dr. Petra Bauer (Siemens AG) "Optimization for SIPLACE Placement Systems"

Präsentation I (Mathematik)

1. Termin (15. Juni 2009)

1. Vortrag Logistik
2. Vortrag Halbleiter-Design
3. Vortrag Digitaldruck

2. Termin (18. Juni 2009)

1. Vortrag Kombinatorische Auktionen
2. Vortrag Clusteranalyse
3. Vortrag Stromproduktion

Präsentation II (Marketing)

1. Termin (Montag, 29. Juni 2009)

1. Vortrag Stromproduktion
2. Vortrag Clusteranalyse
3. Vortrag Kombinatorische Auktionen

2. Termin (Donnerstag, 2. Juli 2009)

1. Vortrag Digitaldruck
2. Vortrag Halbleiter-Design
3. Vortrag Logistik

Hinweise zur Marketing-Präsentation

Während die ersten Präsentationen sich inhaltlich mit den mathematischen Inhalten der Projekte beschäftigt haben, liegt der Schwerpunkt bei den Marketing-Präsentationen auf der Aufbereitung. Jedes Projektteam hat die Aufgabe, zum jeweiligen Projektthema auch eine für eine breite Öffentlichkeit gedachte Aufbereitung zu erstellen, z.B. in Form eines Artikels, eines Podcasts oder einer interaktiven Webseite. Im Rahmen der Marketing-Präsentation stellen die Teams diese Aufbereitung vor (die natürlich noch nicht fertig sein muss). Dabei können etwa folgende Punkte angesprochen werden:
  • Welche Aufbereitungsform wurde gewählt?
  • Was waren die Gründe für die Wahl dieser Aufbereitungsform?
  • Wie eignet sich diese Form für das Projektthema?
  • Welche Zielgruppe wird angesprochen? Welche Voraussetzungen sollen die Adressaten mitbringen?
  • Wie wurde/wird die Aufbereitung technisch realisiert?
  • Welche Probleme gab es evtl. und wie wurden diese gelöst?
  • Welche neuen Erfahrungen hat das Team bei dieser Arbeit gesammelt?
  • Gibt es schon erste vorzeigbare Ergebnisse?
  • Gibt es schon Reaktionen auf die Aufbereitung? Wie kommt das Produkt ggf. bei den Adressaten an?
  • Würde die Entscheidung für eine bestimmte Aufbereitungsform im Nachhinein anders ausfallen, z.B. weil es unerwartete Probleme gab oder weil eine andere Form vielleicht doch besser zum Projektthema gepasst hätte?

Vorbesprechung

  • Vorbesprechung-WWW.pdf: Die Präsentation aus der Vorbesprechung (in leicht gekürzter Fassung)
  • Weiter unten auf dieser Seite finden Sie jetzt kurze Beschreibungen zu den einzelnen Projekten.

Abschlussworkshop

Der Abschlussworkshop findet am Samstag, den 25. Juli 2009, statt (ganztägig). Das genaue Programm stellen wir nach Abschluss der Marketing-Präsentationen vor.

Material (passwortgeschützt)

Mo, 20. April 2009

Do, 23. April 2009

Mo, 27. April 2009

Do, 30. April 2009

  • Wichtige Stichworte für nächste Woche:
    • P und NP, NP-Vollständigkeit
    • Bäume und minimaler Spannbaum
    • Knapsack-Probleme
    • Grundidee der dynamischen Programmierung
    • Matching (Begriff)
    • Traveling Salesman-Probleme, Hamilton-Pfade und Hamilton-Kreise

Mo, 4. Mai 2009

Do, 7. Mai 2009

Mo, 11. Mai 2009

Do, 14. Mai 2009

Mo, 18. Mai 2009

Mo, 25. Mai 2009

  • Wichtige Stichworte für nächste Stunde:
    • LP-Relaxation
    • Polytope, Polyeder
    • Ecken
    • Hyperebenen
    • Normalenkegel
    • Basislösungen

Do, 28. Mai 2009

Mi, 3. Juni 2009

Do, 4. Juni 2009

Mo, 8. Juni 2009

Do, 10. Juni 2009

Mo, 15. Juni 2009

  • Mathematik-Präsentationen der Teams Logistik, Halbleiter-Design und Digitaldruck.

Do, 18. Juni 2009

  • Mathematik-Präsentationen der Teams Kombinatorische Auktionen, Stromproduktion und Clusteranalyse.

Mo, 22. Juni 2009

Mi, 24. Juni 2009: Abitag

  • Aufbau ab ca. 9:00 Uhr, die Poster sollten bis 10:00 Uhr aufgehängt sein.
  • Wer Zeit und Lust hat, kann den Stand schon von 10:00 bis 11:00 Uhr besetzen (Eintreffen der SchülerInnen)
  • Kernzeit: 12:00 - 15:00 Uhr. Während dieser Zeit bitte die Stände besetzt halten
  • ca. 15 - 16 Uhr: Abbau, Poster bitte wieder zu uns bringen
  • ab 16:00 Uhr: "Chill Out" für die SchülerInnen in der Fachschaft - wer Zeit und Lust hat, ist herzlich eingeladen, dort mit den SchülerInnen ins Gespräch zu kommen.

Mo, 19. Juni 2009

  • Marketing-Präsentationen der Teams Kombinatorische Auktionen, Stromproduktion und Clusteranalyse.

Do, 2. Juli 2009

  • Marketing-Präsentationen der Teams Logistik, Halbleiter-Design und Digitaldruck.

Mo, 6. Juli 2009

Sa, 25. Juli 2009

Achtung: Am Montag, dem 6. Juli 2009, ausnahmsweise um 14:15 Uhr im Raum MI 00.07.011!

Inhalte und Methodik (Zusammenfassung: Aushang.pdf)

Überblick über den behandelten Stoff für die Prüfungsvorbereitung. Diese Gliederung geben wir auch an die Prüfer weiter, die diese Vorlesung im Rahmen einer DHP-Prüfung im Umfang von 2 SWS prüfen können.

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 Modellierungen, analysieren die entscheidenden strukturellen Eigenschaften der Probleme und wenden Methoden, die Sie in der Vorlesung kennen lernen, 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 und schließlich ein eintägiger Abschlussworkshop vermitteln Ihnen neben den fachlichen Kenntnissen auch wertvolle Erfahrungen im Projektmanagement, selbstständigem (wissenschaftlichen) Arbeiten und in der Präsentationstechnik.

Vorlesung

Inhaltliche Schwerpunkte der Vorlesung sind unter anderem:
  • ganzzahlige lineare und nichtlineare Optimierung
  • Modellierung von Optimierungsproblemen
  • Schnittebenenverfahren
  • Branch & Bound-Verfahren und Varianten
  • Approximationsalgorithmen und Heuristiken

Praxisprojekt

Mögliche Themen eines Praxisprojekts:
  • Digitaldruck
Ein gewöhnlicher Digitaldrucker verfügt nur über Toner in einer bzw. wenigen ausgewählten Farben, der in sehr kleinen Einheiten ("Pixel") aufgebracht werden kann. Pro Pixel kann also entweder maximale Farbintensität oder keine Farbe gedruckt werden. Um Grauwerte und nicht vorhandene Farben zu drucken, müssen daher eine Vielzahl von Pixeln so positioniert werden, dass aus normalem Betrachtungsabstand der Eindruck einer Mischfarbe entsteht. Dies führt auf das diskrete Optimierungsproblem, die Pixelwerte monochromatischer Bilder (Cyan, Magenta, Gelb, Schwarz) so auf den maximalen oder minimalen Wert zu runden, dass das gedruckte Bild später genauso aussieht wie auf dem Computerbildschirm. Physikalische Prozesse beim Druckvorgang führen zu einer weiteren Herausforderung: Tonerstaub wird mit Hilfe sehr schwacher elektrischer Ladung auf eine Druckfolie aufgebracht. Für ein Pixel allein ist diese Ladung so schwach, dass das Pixel nicht zuverlässig gedruckt werden kann. In der Praxis wird daher das Bild vor dem Druck wie beim klassischen Lichtdruck gerastert und so größere, für das Auge aber aus normalem Betrachtungsabstand nicht einzeln wahrnehmbare Pixelansammlungen erzeugt. Die derzeit gängigen Rastermethoden haben einige Nachteile, insbesondere erzeugen sie sichtbare Texturen im Druckbild (jedenfalls für einige Grautöne). Die Minimierung dieser Texturen war Thema einer Diplomarbeit, die in Kooperation mit Océ Printing Systems GmbH (Poing) entstand. Einige der entwickelten Modelle sind zwar vielversprechend, die Berechnungen erfordern derzeit allerdings sehr viel Zeit. Im Projekt sollen sich die Studierenden die vorhandenen Modelle erarbeiten, erweitern und auf ihre Eigenschaften hin untersuchen. Insbesondere sollen Strategien und Lösungen entwickelt werden, um die Berechnungszeit der auftretenden ganzzahligen linearen Optimierungsprobleme zu verkürzen.

  • Stromproduktion
Elektrische Energie ist kaum speicherbar und muss daher zu jedem Zeitpunkt entsprechend dem Bedarf erzeugt werden. Durch zunehmende Anteile an nur bedingt planbarer, fluktuierender Erzeugung (z.B. Windenergie) sinkt die Bedeutung der charakteristischen Tages- und Saisonalgänge der Verbraucherlast für den Kraftwerkseinsatz. Die Kraftwerksstruktur, d.h. der Zubau weiterer Kraftwerke muss diesem Umstand zukünftig Rechnung tragen. Der Mix aus kalkulierbaren und zufallsabhängigen Randbedingungen führt zu spannenden Optimierungsfragen: Wie kann eine kostenoptimale Stromerzeugung unter Beibehaltung der heutigen Versorgungssicherheit erreicht werden? Welche Kraftwerkstypen kommen dabei zum Einsatz? Ist der Bau und Betrieb von großtechnischen Energiespeichern sinnvoll? Im Projekt soll in Kooperation mit dem Lehrstuhl für Energiewirtschaft und Anwendungstechnik (Prof. Dr.-Ing. U. Wagner, Technische Universität München, Mitarbeit im Verbundforschungsvorhaben "Kraftwerke des 21. Jahrhunderts" ein ausgewähltes praktisches Problem diskutiert, mathematisch formuliert und erforscht werden. Simulationen sollen helfen, die Güte erarbeiteter Lösungen zu quantifizieren.

  • Halbleiterdesign
Beim Design integrierter Halbleiterschaltungen kommt der Frage nach einem energieoptimalen Design immer größeres Gewicht zu. Moderne Mikroprozessoren vereinen hunderte Millionen von Transistoren auf einer Fläche von wenigen Quadratmillimetern und verbrauchen bis zu 100 Watt elektrische Leistung. Ein großer Teil dieser Leistung geht dabei als Abwärme verloren, was zunehmend aufwändige Kühlungsmaßnahmen sowie eine großzügig dimensionierte Energieversorgung notwendig macht. Beides stellt ein massives Problem für mobile, hochintegrierte Geräte wie Notebooks und Handys, aber auch für kritische Einsatzbereiche, z.B. in der Raumfahrt oder in medizinischen Anwendungen (z.B. Steuerelektronik für Implantate) dar. Hauptgrund für die hohe Verlustleistung sind kapazitive Verluste, die für ca. 60% der gesamten Verlustleistung verantwortlich sind (bei steigender Tendenz). Kapazitive Verluste entstehen durch Kopplungseffekte zwischen benachbarten Leitungssegmenten in den Halbleiter-Schaltungen. Durch eine Änderung der Anordnung und Lage der Leitungen zueinander ist es möglich, die Verlustleistung signifikant zu reduzieren. Die Frage nach einer optimalen Platzierung der Leitungen führt auf ein ganzzahliges nichtlineares Optimierungsproblem. Spezielle Eigenschaften der vorliegenden Instanzen ermöglichen das Design eines effizienten Algorithmus zur Bestimmung der Optimallösungen. In diesem Projekt sollen die Studierenden das vorhandene Optimierungsmodell erweitern und die mathematischen Ergebnisse sowie die daraus entwickelten Algorithmen entsprechend anpassen, um auch komplexere Problemsituationen behandeln zu können.

  • Einsatzplanung in der Logistik
Vehicle Scheduling-Probleme verbinden die Planung von Fahrtrouten, die Einhaltung bestimmter Zeitfenster für Ankunft und Abfahrt, die Einsatzplanung für verschiedene Fahrzeuge und die Personalplanung für die Fahrten. Ihre mathematische Modellierung führt auf hochkomplexe Problemstellungen und wird bereits seit längerem in verschiedenen Zusammenhängen erforscht. In diesem Projekt sollen Methoden und Techniken, die für die Lösung der großen und schweren Optimierungsprobleme, die aus Vehicle Scheduling-Modellen entstehen, untersucht und ausprobiert werden. Das kann etwa am Beispiel des Berliner Behindertenfahrdienstes "Telebus" geschehen.

  • kombinatorische Auktionen
Für den Verkauf wertvoller Güter oder die Vergabe großer Aufträge, für die kein vom Markt vorgegebener Preis existiert, wird häufig auf eine Auktion zurückgegriffen. Damit sollen die Marktteilnehmer gezwungen werden, ihre Bewertung zumindest bis zu einem gewissen Grad offenzulegen. Ziel einer Auktion ist es häufig, das Gut dem Bieter zukommen zu lassen, der daraus den größten Nutzen ziehen kann, und folglich bereit ist, den maximalen Preis zu bezahlen. Für verschiedene Auktionsmechanismen (z.B. first price vs. second price auction, verdeckte vs. offene Auktion) lässt sich mit mathematischen Methoden (u.a. Optimierung und Spieltheorie) untersuchen, wie gut diese Ziele jeweils erreicht werden. Neben den einfachen Auktionen spielen in der Praxis kombinatorische Auktionen eine immer wichtigere Rolle. Bei einer kombinatorischen Auktion werden statt einzelner Güter ganze Pakete zusammen versteigert; diese Auktionsform kommt z.B. bei Frequenzvergabeverfahren zum Einsatz, bei denen bestimmte Frequenzen im Paket versteigert werden (das war etwa bei den UMTS-Auktionen der Fall). Bei der Frage nach dem richtigen Auktionsdesign, der Preisermittlung und der Bestimmung des Auktionsgewinners spielen Verfahren der linearen und ganzzahligen Optimierung eine große Rolle.

  • Clusteranalyse von hochdimensionalen Daten mit Messfehlern
Clusteranalyse beschäftigt sich mit dem Problem, eine gegebene Menge von Datenpunkten in mehrere Gruppen mit möglichst ähnlichen, homogenen Datenpunkten zu unterteilen. Zu diesem Zweck sind bereits viele unterschiedliche Clusteralgorithmen entwickelt worden, die in zahlreichen Anwendungsgebieten von großer Bedeutung sind, unter anderem in der Medizin, Biologie, Soziologie oder Telekommunikation. In einem medizinischen Kontext kann ein Datenpunkt beispielsweise durch bestimmte körperliche Merkmale eines Patienten (z.B. Alter und Geschlecht) definiert sein und durch die Werte, die bei diesem Patienten in verschiedenen diagnostischen Tests gemessen wurden. Ein Ziel der Clusteranalyse könnte dann darin bestehen, die untersuchten Patienten in Patientengruppen mit ähnlichen Merkmalen und Symptomen zu unterteilen, um Risikogruppen innerhalb der Patienten zu identifizieren. Probleme dieser Art können als ganzzahlige Optimierungsprobleme formuliert werden, in denen die Clusterzugehörigkeit der Datenpunkte so bestimmt werden soll, dass die ähnlichkeit von Objekten innerhalb eines Clusters maximiert und/oder die ähnlichkeit von Objekten verschiedener Cluster minimiert wird. Einen maßgeblichen Einfluss auf die entstehende Clusterung hat dabei die Wahl des Abstands- bzw. ähnlichkeitsmaßes zweier Punkte oder zweier Cluster, die abhängig von der jeweiligen Problemstellung und den gegebenen Daten getroffen werden muss. Bei der Arbeit mit fehlerhaften Daten spielt zudem die Identifizierung von so genannten Ausreißern eine wichtige Rolle, also von Datenpunkten, deren Werte beispielsweise durch ungenaue Messungen verfälscht wurden und die deutlich isoliert von den restlichen Punkten im Datenraum liegen. Je nach Zweck der Untersuchung kann es äußerst wichtig sein, solche Daten bei der Clusterbildung zu ignorieren, da sie sonst die natürliche Form der Cluster verzerren könnten. Im Rahmen des Projektes sollen sich die Studierenden in die verschiedenen Herangehensweisen von Clusteralgorithmen einarbeiten und untersuchen, welche Methoden und welche Abstandsmaße sich für die Clusterung einer gegebenen Datenmenge eignen. Ein besonderes Augenmerk soll dabei auf den Umgang mit Ausreißern gelegt werden.

Methodik

  • Teamarbeit in Eigenverantwortung
  • Vorlesung
  • praxisnahes Arbeiten
  • Präsentation und Fortschrittsberichte
  • Aufbereitung der Ergebnisse in einer für ein größeres Publikum geeigneten Form
  • Abschlussworkshop

Was haben Sie davon?

  • Seminarschein (bei entsprechendem Engagement)
  • prüfbarer Stoff für eine Diplomprüfung (Umfang 2 SWS) bzw. ECTS-Punkte (3 ECTS)
  • Softskills: Teamarbeit, Multimedia-Kompetenz, Aufbereitung und Vermittlung von Ergebnissen, eigenständiges Arbeiten
  • möglicher Einstieg in eine Abschluss- oder Projektarbeit am Lehrstuhl

Was sollten Sie mitbringen?

  • Grundkenntnisse in linearer und ganzzahliger Optimierung (z.B. aus den Vorlesungen Optimierung 1 & 2)
  • Spaß an praxisnahen Problemstellungen
  • Engagement
  • von Vorteil (aber nicht Voraussetzung) sind Programmierkenntnisse
  • Studierende der Informatik sind willkommen!

Topic revision: r133 - 07 Feb 2011 - 12:38:37 - MichaelRitter
 
Bottomleft LogoBottomright Logo
Impressum  |  Disclaimer und Rechtshinweise  |  AnregungenCopyright Technische Universität München, M9