A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming
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.
|Keywords||linear relaxation, semidefinite relaxation, lift and project, cut polytope, stable set polytope|
|THEME||Logistics (theme 3)|
|Series||CWI. Probability, Networks and Algorithms [PNA]|
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.