Vorlesung Algorithmen zur linearen und diskreten Optimierung

Vorlesung "Algorithmen zur linearen und diskreten Optimierung"

Dozent:  Prof. Dr. R. Schrader
Zeit und Ort:   Mo und Mi 12-13.30
S21 Seminargebäude
Vorlesungsbeginn am 8. April 2013

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 bzw. Scheine 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.