Mathematical Programming and Polyhedral Combinatorics, NOPT034

Summer semester 2021/22

Petr Kolman, Hans Raj Tiwary

Lectures take place every week on Thursday from 9 am in S11. Tutorials take place every other week on Thursday from 12:20 in S8.

Covered topics (by Petr Kolman)

• March 17
  • Introduction, LP in NP∩coNP,
  • Ellipsoid algorithm - part I (how to start).
• March 24
  • Ellipsoid algorithm, part II (the iterative step).
  • Turorial: st-cut by LP of exponential size, separation oracle, optimality, rounding, flow-cut duality.
• March 31
  • Ellipsoid algorithm, part III (the iterative step, contd., when to stop).
• April 7
  • Interior point methods - part I (sketch of the algorithm; potential function; improving direction).
  • Tutorial: How to get rid of the simplifying assumptions for the ellipsoid method (boundness, full dimension); ellipsoid method and semidefinite programming; finding initial solution for the interior point method.
• April 14
  • Interior point methods, part II (decrease of the potential in primal steps; dual step).
• April 21
  • Interior point methods, part III (Decrease of the potential in dual steps; finding the initial pair of strictly feasible solutions
  • Tutorial: Finding optimal vertex solutions from a pair of feasible solutions with small potential. Shortest path and LP duality.

Tentative Syllabus

• 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