Sums-of-squares integer programming relaxation: Lecture 3

by Massimo Lauria

Lecture 3: Improving linear relaxations of integer programs.

Scribe: Mariette Annergren


We discuss methods to improve the linear relaxations of integer programs.

They are systematic ways to find tighter and tighter polytopes containing the convex hull of the integer solutions. The main idea is to lift, that is, to augment the linear program to a higher dimensional space and then to project it down to the original space to obtain a polytope that is smaller than the one we started with. We shall see two different ways to do lift and project: namely the Lovász-Schrijver and Sherali-Adams hierarchies.

Link: [Lecture notes 03]