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

References

• Anjos M. F., Wolkowicz H. Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discrete Appl. Math. (2002) 119:79–106Crossref, Google Scholar
• Balas E., Ceria S., Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Programming (1993) 58:295–324Crossref, Google Scholar
• Barahona F., Mahjoub A. R. On the cut polytope. Math. Programming (1986) 36:157–173Crossref, Google Scholar
• Berg C., Christensen J. P. R., Jensen C. U. A remark on the multidimensional moment problem. Math. Ann. (1979) 243:163–169Crossref, Google Scholar
• Berg C., Christensen J. P. R., Ressel P.Harmonic Analysis and Semigroups—Theory of Positive Definite and Related Functions (1984) (Springer-Verlag, New York) Crossref, Google Scholar
• Chvátal V. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. (1973) 4:305–337Crossref, Google Scholar
• Chvátal V., Cook W., Hartman M. On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. (1989) 114/115:455–499Crossref, Google Scholar
• Cook W., Dash S. On the matrix-cut rank of polyhedra. Math. Oper. Res. (2001) 26:19–30Link, Google Scholar
• Cornuéjols G., Li Y., Aardal K., Gerards A. M. H. On the rank of mixed 0–1 polyhedra. Integer Programming and Combinatorial Optimization 2001 (2001) 71–77Lecture Notes in Computer Science, No. 2081Crossref, Google Scholar
• Curto R. E., Fialkow L. A. The truncated complex K-moment problem. Trans. Amer. Math. Soc. (2000) 352:2825–2855Crossref, Google Scholar
• de Klerk E., Pasechnik D. V. Approximating the stability number of a graph via copositive programming. SIAM J. Optim. (2002) 12:875–892Crossref, Google Scholar
• Eisenbrand F. On the membership problem for the elementary closure of a polyhedron. Combinatorica (2000) 19:299–300Google Scholar
• Eisenbrand F., Schulz A. S., Cornuéjols G., Burkard G., Woeginger R. E. J. Bounds on the Chvátal rank of polytopes in the 0/1 cube. Integer Programming and Combinatorial Optimization 1999 (1999) 137–150Lecture Notes in Computer Science, No. 1610Crossref, Google Scholar
• Fuglede B. The multidimensional moment problem. Expositiones Math. (1983) 1:47–65Google Scholar
• Fujie T., Kojima M. Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. (1997) 10:367–380Crossref, Google Scholar
• Goemans M. X., Tunçel L. When does the positive semidefiniteness constraint help in lifting procedures. Math. Oper. Res. (2001) 26:796–815Link, Google Scholar
• Goemans M. X., Williamson D. P. Improved approximation algorithms for maximum cuts and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. (1995) 42:1115–1145Crossref, Google Scholar
• Grötschel M., Lovász L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer Verlag, Berlin, New York) Crossref, Google Scholar
• Handelman D. Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. (1988) 132:35–62Crossref, Google Scholar
• Haviland E. K. On the momentum problem for distributions in more than one dimension. I, II. Amer. J. Math. (1935) 57:562–568Crossref, Google Scholar
• Haviland E. K. On the momentum problem for distributions in more than one dimension. I, II. Amer. J. Math. (1936) 58:164–168Crossref, Google Scholar
• Lasserre J. B. Optimality conditions and LMI relaxations for 0–1 programs. (2000) . Technical report no. 00099, CNRS-LAAS, Toulouse, FranceGoogle Scholar
• Lasserre J. B. Global optimization with polynomials and the problem of moments. SIAM J. Optim. (2001a) 11:796–817Crossref, Google Scholar
• Lasserre J. B., Aardal K., Gerards A. M. H. An explicit exact SDP relaxation for nonlinear 0–1 programs. Integer Programming and Combinatorial Optimization 2001 (2001b) 293–303Lecture Notes in Computer Science, No. 2081Crossref, Google Scholar
• Lasserre J. B. Semidefinite programming vs. LP relaxations for polynomial programming. Math. Oper. Res. (2002) 27:347–360Link, Google Scholar
• Laurent M. Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure. SIAM J. Optim. (2001) 12:345–375Crossref, Google Scholar
• Laurent M., Grötschel M. Semidefinite relaxations for max-cut. The Sharpest Cut: Festschrift in Honor of M. Padberg's 60th Birthday (2003) (SIAM, Philadelphia, PA) 291–327Google Scholar
• Lovász L. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory (1979) IT-25:1–7Crossref, Google Scholar
• Lovász L., Schrijver A. Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. (1991) 1:166–190Crossref, Google Scholar
• Nesterov Y., Frenk J. B. G., Roos C., Terlaky T., Zhang S. Squared functional systems and optimization problems. High Performance Optimization (2000) (Kluwer Academic Publishers, Utrecht, The Netherlands) 405–440Crossref, Google Scholar
• Parrilo P. A. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. (2000) . Ph.D. thesis, California Institute of Technology, Pasadena, CAGoogle Scholar
• Putinar M. Positive polynomials on compact semialgebraic sets. Indiana Univ. Math. J. (1993) 42:969–984Crossref, Google Scholar
• Reznick B. Some concrete aspects of Hilbert's 17th problem. (1998) . Report 98-002, Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Champaign, ILGoogle Scholar
• Schmüdgen K. The K-moment problem for compact semialgebraic sets. Math. Ann. (1991) 289:203–206Crossref, Google Scholar
• Sherali H. D., Adams W. P. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. (1990) 3:411–430Crossref, Google Scholar
• Sherali H. D., Adams W. P. A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl. Math. (1994) 52:83–106Crossref, Google Scholar
• Sherali H. D., Adams W. P.A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (1999) (Kluwer, Boston, MA) Crossref, Google Scholar
• Sherali H. D., Adams W. P., Driscoll P. J. Exploiting special structures in constructing a hierarchy of relaxations for 0–1 mixed integer problems. Oper. Res. (1998) 46:396–405Link, Google Scholar
• Sherali H. D., Tuncbilek C. H. A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique. J. Global Optim. (1992) 2:101–112Crossref, Google Scholar
• Sherali H. D., Tuncbilek C. H. Reformulation-linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Lett. (1997) 21:1–10Crossref, Google Scholar
• Shor N. Z. An approach to obtaining global extremums in polynomial mathematical programming problems. Kibernetika (1987) 5:102–106Google Scholar
• Shor N. Z.Nondifferentiable Optimization and Polynomial Problems (1998) (Kluwer Academic Publishers, Boston, MA) Crossref, Google Scholar
• Stephen T., Tunçel L. On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. (1999) 24:1–7Link, Google Scholar
• Wilf H. S. Hadamard determinants, Möbius functions, and the chromatic number of a graph. Bull. Amer. Math. Soc. (1968) 74:960–964Crossref, Google Scholar