Vorlesung: Diskrete Optimierung, SS 07

Michael Joswig, Fachbereich Mathematik, TU Darmstadt.

Termine

Achtung: Die Sprechstunde von Andreas am Mo, 28.05.07, wird auf Di, 29.05.07, 11-12 Uhr im Raum S215/336 verlegt.

Achtung: Die Übungen am Mi, 11.07.07, sind Rechnerübungen und finden im PC-Raum S215/K313 statt.

Inhalt

• Modellierung: Ganzzahlige Gleichungs- und Ungleichungssysteme
• Theorie: Ganzzahlige Programme, Polyedrische Kombinatorik
• Methoden: Heuristiken, Exakte Verfahren, Approximation

Literatur

1. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to algorithms. Second edition. MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. MR1848805 (2002e:68001)
2. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization. Second edition. Springer-Verlag, Berlin, 1993. MR1261419 (95e:90001)
3. B. Korte and J. Vygen: Combinatorial Optimization. Theory and algorithms. Second edition. Algorithms and Combinatorics, 21. Springer-Verlag, Berlin, 2002.MR1897297 (2003b:90004)
4. Lior Pachter and Bernd Sturmfels, eds. Algebraic statistics for computational biology. Cambridge University Press, New York, 2005. MR2205865 (2006i:92002)
5. Alexander Schrijver. Theory of linear and integer programming. John Wiley & Sons, Ltd., Chichester, 1986. MR0874114 (88m:90090)
6. Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency. Vol. A,B,C Springer-Verlag, Berlin, 2003. MR1956924 (2004b:90004a)
7. D. A. Cox, J. Little und D. O'Shea, Using algebraic geometry, 2005, Second edition, Springer, New York, MR2122859

Skripten und zusätzliches Material

• Skript: Einführung in die Optimierung (Dür, Martin und Ulbrich) vom WS 06/07
• Skript: Diskrete Optimierung (Martin) vom SS 06
• Buchprojekt: Algorithmische Geometrie (Joswig und Theobald)

Materialien zur Vorlesung

• Beispiel zu Zonotopen mit polymake.
• Folien zu einem Vortrag über Polytope Propagation, gehalten an der ETH Zürich, 2005.

Übungsblätter

Hinweise zur Übung:

• Lösungsvorschlag für die 7. Gruppenübung, sowie die zimpl-Datei und die lp-Datei für CPLEX
• Zum Benutzen von CPLEX muss /opt/bin im Suchpfad (PATH) eingefügt werden.
• Hinweise zur Nutzung von polymake auf den Mathebau-Rechnern stehen unter /home/polymake/README
• Ein Tutorial zur Nutzung von polymake mit Beipielen gibt es hier.