This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Goemans, M. X. Articles by Tunçel, L. Search for Related Content

When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Department of Mathematics, Massachusetts Institute of Technology, Room 2-351, Cambridge, Massachusetts 02139
Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

We study the lift-and-project procedures of Lovász and Schrijver for 0-1 integer programming problems. We prove that the procedure using the positive semidefiniteness constraint is not better than the one without it, in the worst case. Various examples are considered. We also provide geometric conditions characterizing when the positive semidefiniteness constraint does not help.

Key Words: Semidefinite lifting; semidefinite programming; lift-and-project; convex hull; integer programming
History: Received: January 6, 2000; revision received: April 15, 2000;

This article has been cited by other articles:

				K. K. H. Cheung Computation of the Lasserre Ranks of Some Polytopes Mathematics of Operations Research, February 1, 2007; 32(1): 88 - 94. [Abstract] [PDF]

				S. Dash Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs Mathematics of Operations Research, August 1, 2005; 30(3): 678 - 700. [Abstract] [PDF]

				M. Laurent Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope Mathematics of Operations Research, November 1, 2003; 28(4): 871 - 883. [Abstract] [PDF]

				M. Laurent A Comparison of the Sherali-Adams, Lovasz-Schrijver, and Lasserre Relaxations for 0-1 Programming Mathematics of Operations Research, August 1, 2003; 28(3): 470 - 496. [Abstract] [PDF]