A comparison of the Sherali–Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming

A comparison of the Sherali–Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 programming

0.00 Avg rating0 Votes
Article ID: iaor20072070
Country: United States
Volume: 28
Issue: 3
Start Page Number: 470
End Page Number: 496
Publication Date: Aug 2003
Journal: Mathematics of Operations Research
Authors:
Abstract:

Sherali and Adams, Lovász and Schrijver and, recently, Lasserre have constructed hierarchies of successive linear or semidefinite relaxations of a 0–1 polytope PRn 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.

Reviews

Required fields are marked *. Your email address will not be published.