zum Inhalt springen

Vorlesung und Übungen "Algorithmen zur linearen und diskreten Optimierung"

Dozent: Prof. Dr. Michael Jünger

Mo 14-15:30 Uhr im HS II, Physikalische Institute
Mi 14-15:30 Uhr im HS II, Physikalische Institute

Beginn: Mittwoch, 11.10.2017

Inhalte

Die Vorlesung vermittelt die algorithmischen Grundlagen für die mathematischen Methoden des Operations Research zur Lösung NP-vollständiger bzw. NP-schwerer kombinatorischer Optimierungs- und Entscheidungsprobleme.

Nach Einführung der Grundwerkzeuge der Linearen Programmierung 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 durch Branch-and-Bound, Branch-and-Cut sowie Branch-and-Cut-and-Price-Algorithmen. Des Weiteren werden polynomielle Approximationsalgorithmen für NP-schwierige Probleme thematisiert.

Im Laufe der Vorlesung wird eine Auswahl prominenter kombinatorischer Entscheidungs-/Optimierungsprobleme behandelt: Erfüllbarkeitsproblem, Handlungsreisendenproblem, Lineares Ordnungsproblem, Maximum-Schnitt-Problem, Knotenüberdeckungsproblem, Graphfärbungsproblem, Cliquenproblem, Stabile-Mengen-Problem, Rucksackproblem, Kistenpackungsproblem, Maschineneinsatzproblem. In vielen Fällen wird die Diskussion der Algorithmen durch Anwendungsbeispiele in Industrie, Wirtschaft und den Naturwissenschaften motiviert und ergänzt.

Übungen zu "Algorithmen zur linearen und diskreten Optimierung" (mit Dr. Sven Mallach)

In den Übungen zur Vorlesung "Algorithmen zur linearen und diskreten Optimierung" wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben werden unter Anleitung eines Tutors besprochen.

Die zentrale Koordination der Übungen (und auch die Anmeldung hierzu) erfolgt mittels eines ILIAS-Kurses. Es erfolgt eine verbindliche Zuteilung auf die Übungsgruppen zu Beginn der Veranstaltung.