Lecturer
Description
Numerous effective methods for tackling problems in integer programming and combinatorial optimization build on the existence of strong convex relaxations, mainly obtained using linear (LP) and semidefinite programming (SDP). Producing these relaxations is by no means trivial, and it is the subject of much classical and recent research. In this course, we present techniques for producing tight relaxations, or for strengthening simple ones. Covered topics include extended formulations, hierarchies, and cutting plane theory. The main focus will be on theoretical properties.
More about the course can be found here.
Schedule
Friday, 12:1514:00 CM 1221.
Note:
 The course is over! See you at the projects presentations in CM 1221.
Date  Topics  Source 
26/02 
Introduction to the course. Recap of basic theory of polyhedra. Fourier(Motzkin) elimination, Theorems of MinkowskiWeyl and Meyer. 
Introductory slides + Chapters 34 from (1) 
04/03 
Proof of Meyer’s Theorem. Faces of polyhedra. Polyhedrality of the Chvátal closure of rational polyhedra. Application to matching. 
Chapters 345 from (1) + slides 
11/03 
Finite convergence of the iterated Chvátal closure to the integer hull. Complexity of optimizing over the first Chvátal closure. 
Chapter 5 from (1) + notes from next lecture 
18/03 
Caratheodory’s Theorem. The membership problem when the first closure is the integer hull. Upper bounds on the Chvátal rank in the cube. 

25/0301/04 
Easter break. 

08/04 
Introduction to extended formulations. Extended formulations from union of polyhedra, Fourier elimination, description of the projection cone. 

15/04 
Yannakakis’ factorization theorem. Rectangle covering bound. The extension complexity of the correlation polytope. 

22/04 
Extended formulations and communication protocols. 

29/04 
The extension complexity of the stable set and matching polytopes. 

10/05 
Introduction to Cone programming. Approximating the Secondorder cone with a polyhedral cone. 

13/05 
Yannakakis’ theorem for Cone lifts. Positive semidefinite rank. 

20/05 
Lovász’ theta body. Introduction to hierarchies: from sequential convexification to LovászSchrijver. 
See next lecture 
27/05 
SheraliAdams and Lasserre hierarchies. Applications. 

14/06, 14:1517 
Projects presentations:


16/06, 14:1517 
Projects presentations:

Prerequisites
The student should already be familiar with linear programming. Previous exposure to combinatorial optimization and integer programming will be helpful.
Grading
The grading will be based on scribe notes (10%), solution to assignments (30%), and a final project (60%).
Scribe notes
Every student willing to take the exam will be assigned to some lecture, for which (s)he will be in charge of taking detailed notes, typing them in LaTeX, preparing any needed figures, and sending them to the lecturer not later than Tuesday night before the successive lecture.
Please contact the lecturer to agree on the lecture you will scribe.
Literature
The course will be mostly based on recent or less recent research articles. For the part on cutting theory and the theory of (integral) polyhedra, a good source is:
(1) Integer Programming by M. Conforti, G. Cornuéjols, and G. Zambelli (Springer).
Notes will be provided for material not covered by a textbook.