This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Laurent, M. Search for Related Content

A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands
m.laurent{at}cwi.nl

Sherali and Adams (1990), Lovász and Schrijver (1991) and, recently, Lasserre (2001b) have constructed hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope PRⁿ 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.

Key Words: 0–1 polytope; linear relaxation; semidefinite relaxation; lift-and-project; stable set polytope; cut polytope
History: Received: June 22, 2001; revision received: April 5, 2002;revision received: August 19, 2002;

This article has been cited by other articles:

				K. K. H. Cheung Computation of the Lasserre Ranks of Some Polytopes Mathematics of Operations Research, February 1, 2007; 32(1): 88 - 94. [Abstract] [PDF]

				J. A. De Loera, R. Hemmecke, M. Koppe, and R. Weismantel Integer Polynomial Optimization in Fixed Dimension Mathematics of Operations Research, February 1, 2006; 31(1): 147 - 153. [Abstract] [PDF]

				M. Laurent Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope Mathematics of Operations Research, November 1, 2003; 28(4): 871 - 883. [Abstract] [PDF]