Mathematische Methoden der Algorithmik

Lecture: Tuesday, 9:45 - 11:15, SN 19.3.

Tutorial: Wednesday, 15:00 - 16:30, PK 3.1.

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.

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

Homework

The homework sheets will be published here.

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