Strong Relaxations for Discrete Optimization Problems

Lecturer

Dr. Yuri Faenza

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:15-14: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 Minkowski-Weyl and Meyer.

Introductory slides + Chapters 3-4 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 3-4-5 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.

Notes

25/03-01/04

Easter break.

  

08/04

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

Notes

15/04

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

Notes

22/04

Extended formulations and communication protocols.

Notes

29/04

The extension complexity of the stable set and matching polytopes.

Notes

10/05

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

Notes

13/05

Yannakakis’ theorem for Cone lifts. Positive semidefinite rank. 

Notes

20/05

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

See next lecture

27/05

Sherali-Adams and Lasserre hierarchies. Applications.

Notes

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.

 

 

 

  

 

 

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.