Optimierungsalgorithmen und Anwendungen


	Optimierungsalgorithmen und Anwendungen

Inhalt:

Kombinatorische Optimierungsprobleme treten bei vielen praktischen Anwendungen auf (z.B. Flugplanung, Produktionsplanung, Transportplanung, Schichtplanung, Logistik). Nach einer Einführung in verschiedene kombinatorische Optimierungsprobleme werden allgemeine Optimierungsmethoden (exakte und heuristische Verfahren) vorgestellt und an Beispielen aus der Praxis (Scheduling und Transport) illustriert.

Allgemeine Techniken: Branch-and-Bound-Algorithmen, Dynamische Programmierung, Lineare Programmierung, Constraint Programming, Heuristiken, Lokale Suche, Tabusuche, Genetische Algorithmen, Ameisenalgorithmen.

Literatur:

E.H.L. Aarts, J.K. Lenstra: Local Search in Combinatorial Optimization, Wiley, 1997.
P. Brucker, S. Knust: Complex Scheduling, Springer, 2006.
E. Burke, G. Kendall: Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer, 2005.
J. Dreo, A. Petrowski, P. Siarry, E. Taillard: Metaheuristics for Hard Optimization: Methods and Case Studies, Springer, 2006.
M. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
F. Glover, G.A. Kochenberger: Handbook of Metaheuristics, Kluwer, Boston, 2003.
F. Glover, M. Laguna: Tabu Search, Kluwer, Boston, 1997.
T. Grünert, S. Irnich: Optimierung im Transport, Band I: Grundlagen, Shaker, 2005.
Z. Michalewicz, D.B. Fogel: How to Solve It: Modern Heuristics, Springer, 2004.
C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization, Prentice Hall, Englewood Cliffs, N.J., 1982.
C.R. Reeves: Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993.

Software:

Zur Lösung von LP- und MIP-Problemen soll in den Übungen die ZIB Optimization Suite eingesetzt werden, die die Programme Zimpl, SCIP und SoPlex enthält. Diese sind für den akademischen Einsatz frei verfügbar. Die Programme sind auf den Rechnern im CIP-Pool (31/339) installiert; wer möchte, kann sie aber auch auf dem eigenen Computer verwenden.

Um Zimpl bzw. SCIP in allen Verzeichnissen ausführen zu können, müssen Sie das Installationsverzeichnis in der PATH Variable hinzufügen. Eine Beschreibung dazu finden Sie z.B. hier

Teilnahme:

Die Veranstaltung ist vorgesehen für M.Sc. ab dem 1. Semester. Teilnehmen können alle interessierten Studierenden aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science.

Schein:

Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige Teilnahme an den Übungen, die erfolgreiche Bearbeitung der Übungsaufgaben (jeweils 50% der Maximalpunkte in theoretischen und 50 % der Maximalpunkte in praktischen Aufgaben) und die erfolgreiche Absolvierung einer Prüfung am Ende des Semesters. Prüfungsrelevant sind alle Kapitel der Vorlesung sowie die Themen aus den Übungen.