Mathematische Methoden der Algorithmik

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

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

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

Mailing list

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

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

Homework

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