Sherali and Adams [SA90], Lovász and Schrijver [LS91] and, recently, Lasserre [Las01b] have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite relaxations of a 0-1 polytope P⊆ Rn 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.
Additional Metadata
Keywords linear relaxation, semidefinite relaxation, lift and project, cut polytope, stable set polytope
THEME Logistics (theme 3)
Publisher CWI
Series CWI. Probability, Networks and Algorithms [PNA]
Citation
Laurent, M. (2001). A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming. CWI. Probability, Networks and Algorithms [PNA]. CWI.