Mathematische Methoden der Algorithmik

Vorlesung: Dienstag, 9:45 - 11:15, SN 19.4.

Übung: Mittwoch, 15:00 - 16:30, IZ 161.

Studienleistung: Erreichen von mindestens 50 Prozent der Hausaufgabenpunkte.

Prüfungsleistung: Mündliche Prüfung oder Klausur.

Das Modul behandelt die lineare und ganzzahlige Optimierung. Die Studierenden erlernen, gegebene Probleme als lineare Programme zu formulieren und zu lösen, sowie die theoretischen Aspekte dahinter:

1. Lineare Optimierung
2. Simplexalgorithmus
3. Dualität
4. Ganzzahlige Optimierung

Die Hauptreferenz für diesen Kurs ist Linear Programming: Foundations and Extensions von Robert J. Vanderbei (SpringerLink). Es gibt aber noch deutlich mehr Literatur zu den Themen dieses Kurses.

1. Matousek and Gärtner: Understanding and Using Linear Programming (Springer).
2. A. Schrijver: Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1998 (s-tlip-98, BibTeX)
3. V. Chvátal: Linear Programming, Series of Books in the Mathematical Sciences, W.H. Freeman, 1983 (c-lp-83, BibTeX)
4. Einführung in die Mathematische Optimierung - Burkard und Zimmermann Freier Zugang im Uni-Netzwerk.

Mailingliste

Bei Interesse meldet Euch bitte auf jeden Fall auf der Mailingliste an!

Material

Lecture 1: Chapter 1, part of Chapter 2

Tutorial 1: Slides, Notebook (PDF), Notebook (.ipynb)

Lecture 2: Chapter 2

Lecture 3: Chapter 3

Tutorial 3: Degeneracy is rare in small instances (.py)

Lecture 4: Chapter 4, Average case analysis (.py)

Lecture 5: Chapter 5 part 1

Lecture 6: Chapter 5 part 1 and part 2

Lecture 7: Chapter 6 part 1

Lecture 8: Chapter 6 part 1 and part 2

Lecture 9: Chapter 7

Lecture 10: Chapter 8

Lecture 11: Chapter 9

Lecture 12: Chapter 10

Lecture 13: Chapter 11

Hausaufgaben

1. Homework Sheet 1
2. Homework Sheet 2
3. Homework Sheet 3
4. Homework Sheet 4
5. Homework Sheet 5