In der Vorlesung werden die theoretischen und algorithmischen Grundlagen zur Lösung NP-vollständiger Probleme der kombinatorischen sowie der allgemeinen diskreten Optimierung vermittelt.
Nach Einführung der Grundwerkzeuge der linearen Optimierung und der Komplexitätstheorie behandelt die Vorlesung insbesondere Algorithmen der linearen (gemischt-) ganzzahligen und kombinatorischen Optimierung. Der Schwerpunkt liegt in der exakten Lösung gemischt-ganzzahliger Entscheidungs- und Optimierungsprobleme über verschiedene Relaxierungstechniken (lineare, Lagrange, semidefinite) in Verbindung mit Branch-and-Bound-, Branch-and-Cut- sowie Branch-and-Cut-Price-Ansätzen. Desweiteren werden polynomielle Approximationsalgorithmen für NP-schwierige Probleme thematisiert und an bekannten Problemklassen (SAT, TSP, Färbung, Clique, stabile Menge, Schnitte, Rucksack) erläutert.Die Vorlesung wird 4-stündig mit Übungen (2-stündig) angeboten. Die Leistungspunkte können durch Teilnahme an den Übungen und der Abschlussklausur erworben werden.
- R.E. Burkard, U.T. Zimmerann: Einführung in die Mathematische Optimierung, Springer
- U. Faigle, W. Kern, G. Still: Algorithmic Principles of Mathematical Programmimg, Kluwer
- G. Nemhauser, L. Wolsey: Integer and Combinatorial Optimization, Wiley
- A. Schrijver: Theory of Linear and Integer Programming, Wiley
- L. Wolsey: Integer Programming, Wiley
In den Übungen wird der Inhalt der Vorlesung vertieft und es besteht die Möglichkeit, den Vorlesungsstoff zu diskutieren. Zusätzlich werden in den Übungen die Aufgaben besprochen und es wird eine intensive Prüfungsvorbereitung stattfinden.
Die Folien der Vorlesung werden jeweils hier zur Verfügung gestellt.