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
- February 20 (PK)
- Introduction.
- Fourier Motzkin elimination and Farkas lemma.
- Elementary definitions - convex hall, cone, Minkowski sum, H-polyhedron and V-polyhedron.
- February 27 (PK)
- Ellipsoid algorithm, part I - overview, how to start.
- March 5 (PK)
- Ellipsoid algorithm, part II - the iterative step.
- March 12
- Ellipsoid algorithm, part III - when to stop, how to get rid of the simplifying assumptions.
- March 19
- Interior point methods, part I - sketch of the algorithm; potential function; improving direction.
- March 26
- Interior point methods, part II - decrease of the potential in primal steps; dual step.
Tentative Syllabus
- Polyhedra/Polytopes: basic notions, face lattice, polar duality
- Ellipsoid algorithm for linear programming
- Interior point methods for linear programming
- Extended formulations
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