On the Matrix-Cut Rank of Polyhedra

Abstract

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.