Mathematische Methoden der Algorithmik

Lecture: Tuesday, 9:45 - 11:15, IZ 305.

Tutorial: Wednesday, 15:00 - 16:30, IZ 305.

Studienleistung: 50 percent of the homework.

''Prüfungsleistung'': Oral or written exam.

The topic is linear and integer programming. Besides the theoretical basics, the students learn to model problems as such programs and how to solve them:

1. Linear optimization
2. Simplex algorithm
3. Duality
4. Integer optimization

The main reference for this course is Linear Programming: Foundations and Extensions by Robert J. Vanderbei (SpringerLink). There is a lot of additional literature on the topic:

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 Free access from the university network.

Mailing list

If you are interested in the course, please register for the mailing list!

Material

The learning material will be published here.

Vorlesung 00: Intro [pdf]

Vorlesung 01: Simplex-Algorithmus [pdf]

Vorlesung 02: Fundamentalsatz [pdf]

Vorlesung 03: Dualität I [pdf][Notizen]

Vorlesung 04: Dualität II [pdf]

Vorlesung 05: Matrix Notation [pdf]

Vorlesung 06: Implementationen [pdf]

Vorlesung 07: Allgemeine LPs[pdf]

Vorlesung 08: Integer Programming [pdf]

Vorlesung 09: Graphenprobleme [pdf]

Vorlesung 10: Matching Polytop [pdf]

Vorlesung 11: Geometrische Probleme [pdf]

Vorlesung 12: Zusammenfassung [pdf]

Übungen

• Übung 1: Lineare Algebra, Modellierung [pdf]
• Übung 2: Dualität, Komplementärer Schlupf [pdf]

Homework

• Blatt 1, Abgabe 13.11., 15 Uhr: [pdf]
• Blatt 2, Abgabe 27.11., 15 Uhr: [pdf]

The homework sheets will be published here.

Klausur

Die Klausur findet am 14.03.25 von 13-15 Uhr im Raum PK 11.2 statt. Bitte seid 15 Minuten vorher anwesend. Benötigt wird ein dokumentenechter Stift und der Studierendenausweis. Eigenes Papier oder Unterlagen sind nicht erlaubt.