A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

Mathematics of Operations Research - Tập 28 Số 3 - Trang 470-496 - 2003
Monique Laurent1
1CWI Kruislaan 413 1098 SJ Amsterdam, The Netherlands

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

10.1016/S0166-218X(01)00266-9

10.1007/BF01581273

10.1007/BF02592023

10.1007/BF01420423

10.1007/978-1-4612-1128-0

10.1016/0012-365X(73)90167-2

10.1016/0024-3795(89)90476-X

10.1287/moor.26.1.19.10593

10.1007/3-540-45535-3_6

10.1090/S0002-9947-00-02472-7

10.1137/S1052623401383248

Eisenbrand F., 2000, Combinatorica, 19, 299

10.1007/3-540-48777-8_11

Fuglede B., 1983, Expositiones Math., 1, 47

10.1023/A:1008282830093

10.1287/moor.26.4.796.10012

10.1145/227683.227684

10.1007/978-3-642-97881-4

10.2140/pjm.1988.132.35

10.2307/2371187

10.2307/2371063

10.1137/S1052623400366802

10.1007/3-540-45535-3_23

10.1287/moor.27.2.347.322

10.1137/S1052623400379371

Laurent M., 2003, The Sharpest Cut: Festschrift in Honor of M. Padberg's 60th Birthday, 291

10.1109/TIT.1979.1055985

10.1137/0801013

10.1007/978-1-4757-3216-0_17

Parrilo P. A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization (2000) Ph.D. thesis, California Institute of Technology, Pasadena, CA

10.1512/iumj.1993.42.42045

10.1007/BF01446568

10.1137/0403036

10.1016/0166-218X(92)00190-W

10.1007/978-1-4757-4388-3

10.1287/opre.46.3.396

10.1007/BF00121304

10.1016/S0167-6377(97)00013-8

Shor N. Z., 1987, Kibernetika, 5, 102

10.1007/978-1-4757-6015-6

10.1287/moor.24.1.1

10.1090/S0002-9904-1968-12104-4

Thông tin
Thông tin xuất bản

Mathematics of Operations Research

Tập 28 Số 3

470-496

Thông tin tác giả