Mathematische Methoden der Algorithmik

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

Übung: Mittwoch, 15:00 - 16:30, PK 3.1.

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

Hier werden die Vorlesungsmaterialien veröffentlicht.

Lecture 1: Chapter 1 slides

Big-Tutorial 1, Lecture 2 and part 1 of Big-tutorial 2: Chapter 2 slides

Small-Tutorial 1: the slides + the code

Lecture 3 and part 2 of Big-Tutorial 2 : Chapter 3 slides

part 3 of Big-Tutorial 2, Lecture 4, Lecture 5, part 1 of Big-Tutorial 3 : Chapter 5 slides

Lecture 6: Chapter 4 slides + the code

Lecture 7: Chapter 6 slides

Tutorial on Primal Simplex (Matrix Notation): Jupyter Notebook or PDF version

Lecture 8: Chapter 7 slides

Lecture 9: Chapter 8 slides

Tutorial on implementation issues: Jupyter Notebook or PDF version

Lectures 10 and 11: Chapter 9 slides

Tutorial on modeling and cutting planes: Jupyter Notebook or HTML version

Lecture 12 on the TSP: Chapter 10 slides

Hausaufgaben

Hier werden die Hausaufgabenblätter veröffentlicht.

The first set of homework exercises with due date 29.11.2023 : homework01

The second set of homework exercises with due date 13.12.2023 : homework02

The third set of homework exercises with due date 10.01.2024 : homework03

The fourth set of homework exercises with due date 24.01.2024 : homework04

The fifth set of homework exercises with due date 07.02.2024 : homework05