Mathematical Programming and Polyhedral Combinatorics, NOPT034

Summer semester 2024/25

Petr Kolman, Hans Raj Tiwary

The scheduling of the lectures will be decided at the beginning of the semester; you can affect the scheduling by participating in the voting.

Syllabus

• structure of polytopes and the complexity of their description,
• 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.

Tentative Programme

• Polyhedra/Polytopes: basic notions, face lattice, polar duality
• Ellipsoid algorithm for linear programming
• Interior point methods for linear programming
• Extended formulations

Textbooks, Lecture Notes

• Textbook Lectures on Polytopes by Guenter M. Ziegler - available in the University library at Mala Strana.
• Lecture notes on the ellipsoid algorithm by M. Goemans
  
• Lecture notes on interior point method by M. Goemans (see chapter 13)
  
• Textbook Linear Programming by Howard Karloff, chapters 4 and 5 - available in the University library at Mala Strana.
• Lecture notes on polynomial time LP algorithms by P. Kolman (in Czech)
  

Other courses on Combinatorial Optimization

• Combinatorial Optimization by Michel Goemans at MIT
• Linear and Semidefinite Programming by Anupam Gupta and Ryan O'Donnell at CMU