zum Inhalt springen

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

Dozent: Prof. Dr. Michael Jünger

Mo 12-13:30 Uhr im HS 301 Pohligstr. 1
Mi 12-13:30 Uhr im HS 301 Pohligstr. 1

Beginn: Montag, 02.04.2012

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. Vorlesungen und Übungen für Master-Studierende vermitteln neben vertieften Fachkenntnissen aus dem jeweiligen Bereich auch allgemein weitergehende Fähigkeiten zur Einordnung, Erkennung, Formulierung und Lösung von Problemstellungen durch konzeptionelles, analytisches und logisches Denken. Die Übungen können neben der Vertiefung des Vorlesungsstoffs auch dem Erwerb von Kommunikationsfähigkeiten und Präsentationskompetenz dienen.

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" (gemeinsam mit Sven Mallach)

In den Übungen wird der Vorlesungsstoff vertieft. Schriftliche Übungsaufgaben werden unter Anleitung eines Tutors besprochen. Die Übungen finden wöchentlich statt.

 

E-Learning (ILIAS)

Zum zugehörigen ILIAS-Bereich

 

Klausurtermine

1. Klausur: 19.07.2012   13-15 Uhr   Hörsaal Physik I

2. Klausur: 25.09.2012   10-12 Uhr   Hörsaal Physik I