On the matrix-cut rank of polyhedra

Lovasz and Schrijver 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 Chvatal rank 1, that meets this worst case bound of n. We describe another example requiring n iterations even when combining the semidefinite and Gomory–Chvatal 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.