Vorlesung Algorithmen zur linearen und diskreten Optimierung

Vorlesung "Algorithmen zur linearen und diskreten Optimierung"

Dozent:  Prof. Dr. R. Schrader
Mo. und Mi. 10 -11.30 im Hörsaal H230 im COPT-Gebäude
Vorlesungsbeginn: 17. Oktober 2016
Raumänderung: ab Mittwoch, den 23.11.2016 findet die Vorlesung im Hörsaal XXXI, alte Botanik statt.

Inhalt der Vorlesung

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.

Literatur

Übungen

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.

Skript

Die Folien der Vorlesung werden jeweils  hier  zur Verfügung gestellt.