Kombinatorische Optimierung 1

Diese Lehrveranstaltung befasst sich mit grundlegenden kombinatorischen Optimierungsproblemen. In der Regel sind das polynomial lösbare Optimierungsprobleme, für die sowohl strukturelle Eigenschaften als auch Lösungsansätze besprochen werden. Das Ziel ist, einerseits die Studierenden mit prominenten, sowohl theoretisch als auch praktisch relevanten Problemen der Kombinatorischen Optimierung vertraut zu machen, und andererseits eine Handvoll an Lösungsansätzen und algorithmischen Paradigmen als praktisch relevantes Wissen zu vermitteln.

Kapitel und Stichwörter

• Aufspannende Bäume und Arboreszenzen: minimale aufspannende Bäume, Arboreszenzen mit minimalem Gewicht (das Spannbaum-Polytop).
• Kürzeste Wegeprobleme: kürzeste Wege von einer Quelle aus (Dijkstras Algorithmus, Moore-Bellman-Ford-Algorithmus), kürzeste Wege zwischen allen Knotenpaaren (Floyd-Warshall-Algorithmus), Kreise mit minimalem durchschnittlichem Kantengewicht, Ansätze zur Lösung von „large-scale“-Instanzen.
• Netzwerkflüsse: Max-Flow-Min-Cut-Theorem, Satz von Menger, Edmonds-Karp-Algorithmus, Push-Relabel-Algorithmus, Gomory-Hu-Bäume, Ansätze zur Lösung von „large-scale“-Instanzen.
• Flüsse mit minimalen Kosten: Optimalitätskriterium, Minimum-Mean-Cycle-Cancelling-Algorithmus, sukzessive-Kürzeste-Wege-Algorithmus, Ansätze zur Lösung von „large-scale“-Instanzen.
• Matching-Probleme: maximales Matching in bipartiten und beliebigen Graphen, gewichtetes Matching in bipartiten Graphen und lineares Zuordnungsproblem (Matching-Polytop).
• Matroide: Definition, Greedy-Algorithmus (Schnitt von zwei Matroiden).
• (Ganzzahlige Optimierung: ganzzahlige Hülle eines Polyeders, vollständige duale Ganzzahligkeit, vollständig unimodulare Matrizen, Schnittebenen, Lagrange-Relaxierung.)

Die Hauptliteraturquelle ist:

Weitere Literatur

• R. Ahuja, T. Magnanti und J. Orlin, Network Flows: Theory, Algorithms and Applications , Prentice Hall, 1993.
• L. Chen, R. Kyng, Y.P. Liu, R. Peng, M.P. Gutenberg und S. Sachdeva, Maximum flow and minimum cost flow in almost linear times , arXiv, 2022. Siehe auch den populärwissenschaftlichen Bericht in Quanta Magazine .
• W. Cook, W. Cunningham, W. Pulleyblank und A. Schrijver, Fast robust shortest paths computations , ATMOS, 2018.
• C. Hansknecht, A. Richter und S. Stiller, Combinatorial Optimization , Wiley, 1998.
• W. Hochstättler und A. Schliep, CATBox: An Interactive Course in Combinatorial Optimization , Springer, 2010.
• S. Krumke und H. Noltemeier, Graphentheoretische Konzepte und Algorithmen , Teubner, 2005.
• A. Schrijver, Combinatorial Optimization, Volume A , Springer, 2003.

Die Vorlesung wird anhand einer einer mündlichen Prüfung benotet. Der erster Prüfungstermin wird in der ersten Februarwoche stattfinden, das genaue Datum wird rechtzeitg bekanntgegeben. Die weiteren Termine, mindestens 3 Termine im Sommersemester 2027, stehen noch nicht fest.

Die einstündige Übung hat einen immanenten Charakter und wird anhand einer Klausur und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe eines Punktesystems (Kreuzesystem) benotet. Zur Mitarbeit zählt insbesondere die Präsentation der Lösungen der Übungsbeispiele.

Klausur

Klausurtermin: Am Ende des Semesters; das genaue Datum wird noch bekanntgegeben.

Nachklausur: Bei Bedarf in der letzten Woche der Semesterferien oder in der ersten Woche des Sommersemesters 2027. Der Termin wird rechtzeitig bekannt gegeben.

Mitarbeit in den Übungseinheiten

Für die individuelle Ausarbeitung der Lösungen der Übungsaufgaben bekommt man höchstens 3 Punkte . Für ein positives Übungszeugnis muss jeder Studierende mindestens einmal die Lösung einer Übungsaufgabe präsentieren . Jede Tafelmeldung ist maximal 4 Punkte wert. Für besondere Leistungen können maximal 2 Bonuspunkte erworben werden.

Bei der Klausur können maximal 20 Punkte erworben werden. Für ein positives Übungszeugnis müssen bei der Klausur mindestens 10 Punkte erreicht werden.

Berechnung der Gesamtpunkte

Notenschlüssel

Die maximale erreichbare Punktezahl ist 31 (ohne Bonuspunkte).

Ein Katalog von Übungsaufgaben (PDF) ist auf der Seite der Lehrveranstaltung im TeachCenter → verfügbar.