Kombinatorische Optimierung

Dr. Michael Stiglmayr

Inhalt

Kombinatorische Optmierungsprobleme sind Optimierungsprobleme, die auf strukturierten Mengen definiert sind und unterscheiden sich dadurch von allgemeinen diskreten (ganzzahligen/binären)
Optimierungsproblemen. Diese zugrundeliegenden Strukturen können z. B. Graphen, Netzwerke oder Teilmengensysteme sein. Im Rahmen dieser Vorlesung werden wir uns insbesondere mit den folgenden Themen beschäftigen:

• Rucksackproblem
• Zuweisungsproblem, Matching Probleme
• verallgemeinerte Netzwerk-Flussprobleme: Fixed-charge network flow, Multicommodity flow
• Komplexitätstheorie
• Gültige Ungleichungen

Voraussetzungen

Das Seminar richtet sich an Studierende im Master Mathematik. Grundkenntnisse in Optimierung, insbesondere aus der Vorlesung "Operations Research II – Diskrete Optimierung“, werden vorausgesetzt. Außerdem sind Programmierkenntnisse (z. B. in Matlab) zur Bearbeitung einiger
Übungsaufgaben notwendig.

Termine

Vorlesung: Dienstag 10–12 Uhr, Donnerstag 8–10 Uhr
Übung: Montag 8–10 Uhr

Moodle

https://moodle2.uni-wuppertal.de/course/view.php?id=8982

Literatur

• R. Burkard, M. Dell’Amico und S. Martello. Assignment Problems. SIAM, Philadelphia, 2009.
• H. Kellerer, U. Pferschy und D. Pisinger: Knapsack Problems, Springer, 2004
• B. Korte und J. Vygen. Kombinatorische Optimierung – Theorie und Algorithmen. Springer, 2012.
• C. H. Papadimitriou und K. Steiglitz. Combinatorial Optimization – Algorithms and Complexity. Dover Publications, 1998.