A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Tóm tắt
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 P ⫅ ℝ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.
Từ khóa
Tài liệu tham khảo
Eisenbrand F., 2000, Combinatorica, 19, 299
Fuglede B., 1983, Expositiones Math., 1, 47
Laurent M., 2003, The Sharpest Cut: Festschrift in Honor of M. Padberg's 60th Birthday, 291
Parrilo P. A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (2000) Ph.D. thesis, California Institute of Technology, Pasadena, CA
Shor N. Z., 1987, Kibernetika, 5, 102