A comparison of the Sherali-Adams, Lovasz-Schrijver, and Lasserre relaxations for 0-1 programming

• 成果类型: Article
• 署名作者: Laurent, M
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.28.3.470.16391
• 发表日期: 2003
• 页码: 470-496
• 关键词: semidefinite relaxations; momentum problem; cut; POLYNOMIALS; hierarchy; approximation; number; rank

摘要

Sherali and Adams (1990), Lovasz and Schrijver, (1991) and, recently, Lasserre (2001b) have constructed hierarchies of successive linear or semidefinite relaxations of a 0-1 polytope P subset of or equal to R-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.