A comparison of the Sherali-Adams, Lov\'asz-Schrijver and Lasserre relaxations for $0-1$ programming

Monique Laurent (moniquecwi.nl)

Abstract: Sherali and Adams \cite{SA90}, Lov\'asz and Schrijver \cite{LS91} and, recently, Lasserre \cite{Las01b} have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a $0-1$ polytope $P\subseteq \oR^n$ converging to $P$ in $n$ steps. Lasserre's approach uses results about representations of positive polynomials as sums of squares and the dual theory of moments. We present the three methods in a common elementary framework and show that the Lasserre construction provides the tightest relaxations of $P$. As an application this gives a direct simple proof for the convergence of the Lasserre's hierarchy. We describe applications to the stable set polytope and to the cut polytope.

Keywords: linear relaxation, semidefinite relaxation, lift and project, stable set polytope, cut polytope

Category 1: Integer Programming

Category 2: Combinatorial Optimization

Category 3: Linear, Cone and Semidefinite Programming

Citation: Mathematics of Operations Research, 28(3):470--496, 2003

Download:

Entry Submitted: 06/29/2001
Entry Accepted: 06/29/2001
Entry Last Modified: 09/26/2003

Modify/Update this entry