Mathematical Programming and Polyhedral Combinatorics, NOPT034

Summer semester 2023/24

Petr Kolman, Hans Raj Tiwary

Lectures take place every week on Tuesday from 9 am in S8. Tutorials take place on Tuesday from 8:15 in S8.

Tentative Syllabus

This is a master-level course focusing on two topics in combinatorial optimization: i) structure of polytopes and the complexity of their description, ii) efficient methods for optimization over polytopes (and polyhedra).

In the first part of the lecture, we will cover basics of the theory of polytopes such as the Minkowski-Weyl theorem, face-lattice, 1-skeleton, etc. In the second part we describe in detail the ellipsoid algorithm and the interior point methods (IPMs). It is worth mentioning that the framework of IPMs is a key ingredient of the recent algorithm for exact maximum flow in almost linear time.

Covered topics

Tentative Syllabus

Course Credit

You are supposed to do a project in linear programming - check the details. In case of any questions, please let me know.

Textbooks, Lecture Notes

Other courses on Combinatorial Optimization

March 26, 2024