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] [Beispiel]

Vorlesung 06: Implementationen [pdf]

Vorlesung 07: Allgemeine LPs[pdf]

Vorlesung 08: Integer Programming [pdf]

Vorlesung 09: Graphenprobleme [pdf] [Notizen]

Vorlesung 10: Matching Polytop [pdf]

Vorlesung 11: Traveling Salesman Problem [pdf]

Vorlesung 12: Zusammenfassung [pdf]

Übungen

• Übung 1: Lineare Algebra, Modellierung [pdf]
• Übung 2: Dualität, Komplementärer Schlupf [pdf]
• Übung 3: Phase 1, Bipartite Matchings [pdf]
• Übung 4: Allgemeine LPs, Recap [pdf]
• Übung 5: Branch-and-Cut [pdf]
• Übung 6: Modellierung, Cutting Planes [pdf]

Homework

• Blatt 1, Abgabe 13.11.24, 15 Uhr: [pdf]
• Blatt 2, Abgabe 27.11.24, 15 Uhr: [pdf]
• Blatt 3, Abgabe 11.12.24, 15 Uhr: [pdf]
• Blatt 4, Abgabe 08.01.25, 15 Uhr: [pdf]
• Blatt 5, Abgabe 22.01.25, 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, ein Lineal (oder Geodreieck) und der Studierendenausweis. Eigenes Papier, Unterlagen oder andere Hilfsmittel sind nicht erlaubt.

Die Ergebnisse der Klausur sind da. Die Note kann TU-Connect entnommen werden. Dem [pdf] können Statistiken, sowie die Punktzahlen der eigenen Klausur entnommen werden. Zusammen mit der letzten Ziffer der Matrikelnummer plus die Note ist die Punktzahl (fast) eindeutig.

Die Einsicht soll am 20.03. um 13 Uhr im Raum IZ 313 stattfinden. Bitte gebt kurz eine Rückmeldung, ob ihr eure Klausur einsehen möchtet.