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 Cook, W. Articles by Dash, S. Search for Related Content

On the Matrix-Cut Rank of Polyhedra

Computational and Applied Mathematics, Rice University, Houston, Texas 77005
Computational and Applied Mathematics, Rice University, Houston, Texas 77005

Lovász and Schrijver (1991) described a semidefinite operator for generating strong valid inequalities for the 0-1 vectors in a prescribed polyhedron. Among their results, they showed that n iterations of the operator are sufficient to generate the convex hull of 0-1 vectors contained in a polyhedron in n-space. We give a simple example, having Chvátal rank 1, that meets this worst case bound of n. We describe another example requiring n iterations even when combining the semidefinite and Gomory-Chvátal operators. This second example is used to show that the standard linear programming relaxation of a k-city traveling salesman problem requires at least k/8 iterations of the combined operator; this bound is best possible, up to a constant factor, as k+1 iterations suffice.

Key Words: Semidefinite programming; integer hull; rank of polytopes; cutting planes; projection operators
History: Received: October 27, 1999; revision received: August 14, 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]

				M. X. Goemans and L. Tuncel When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures? Mathematics of Operations Research, November 1, 2001; 26(4): 796 - 815. [Abstract] [PDF]