Strong Relaxations for Discrete Optimization Problems


Dr. Yuri Faenza


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.


Friday, 12:15-14:00 CM 1221.


  • The course is over! See you at the projects presentations in CM 1221.


Date Topics Source


Introduction to the course. Recap of basic theory of polyhedra. Fourier(-Motzkin) elimination, Theorems of Minkowski-Weyl and Meyer.

Introductory slides + Chapters 3-4 from (1)    


Proof of Meyer’s Theorem. Faces of polyhedra. Polyhedrality of the Chvátal closure of rational polyhedra. Application to matching.

Chapters 3-4-5 from (1) + slides


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


Caratheodory’s Theorem. The membership problem when the first closure is the integer hull.  Upper bounds on the Chvátal rank in the cube.



Easter break.



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



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



Extended formulations and communication protocols.



The extension complexity of the stable set and matching polytopes.



Introduction to Cone programming. Approximating the Second-order cone with a polyhedral cone. 



Yannakakis’ theorem for Cone lifts. Positive semidefinite rank. 



Lovász’ theta body. Introduction to hierarchies: from sequential convexification to Lovász-Schrijver.

See next lecture


Sherali-Adams and Lasserre hierarchies. Applications.


14/06, 14:15-17

Projects presentations:

  • Claudiu Valculescu: 0/1 Polytopes with quadratic Chvatal rank, by T. Rothvoss and L. Sanità.

  • Thang Pham: The Chvátal-Gomory Closure of a Strictly Convex Body, by  D. Dadush, S. Dey, and J.P. Vielma.

  • Hossein Mojarrad: The Projected Faces Property and Polyhedral Relations by M. Conforti and K. Pashkovich.

  • Manuel Aprile: Constructing Extended Formulations from Reflection Relations by V. Kaibel and K. Pashkovich.


16/06, 14:15-17

Projects presentations:

  • Jakub Tarnawski: Common information and unique disjointness by G. Braun and S. Pokutta.

  • Christoph Hunkenshroeder: Approximate constraint satisfaction requires large LP relaxations by Chan, Lee, Raghavendra, and Steurer.

  • Natalia Karaskova will talk about the relation between quantum communication complexity and extended formulations, partially based on Exponential Lower bounds for polytopes in Combinatorial Optimization, by S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf.
  • Igor Malinovic: A Lasserre-based (1+ε)-approximation for Pm | p_j = 1,prec |C_max by T. Rothvoss.








The student should already be familiar with linear programming. Previous exposure to combinatorial optimization and integer programming will be helpful.


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.


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.