Small Chvatal Rank

Tristram Bogart(bogartmath.washington.edu)
Rekha Thomas(rrthomasu.washington.edu)

Abstract: We introduce a new measure of complexity of integer hulls of rational polyhedra called the small Chvatal rank (SCR). The SCR of an integer matrix A is the number of rounds of a Hilbert basis procedure needed to generate all normals of a sufficient set of inequalities to cut out the integer hulls of all polyhedra {x: Ax <= b} as b varies. The SCR of A is bounded above by the Chvatal rank of A and is hence finite. We exhibit examples where SCR is much smaller than Chvatal rank. When the number of columns of A is at least three, we show that SCR can be arbitrarily high proving that, in general, SCR is not a function of dimension alone. For polytopes in the unit cube we provide a lower bound for SCR that is comparable to the known lower bounds for Chvatal rank in that situation. Lastly, we establish the connection between SCR and the notion of supernormality.

Keywords: polyhedron, polytope, integer hull, cutting planes

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: University of Washington Department of Mathematics Box 354350 Seattle, WA 98195-4350

Download: [PDF]

Entry Submitted: 07/20/2007
Entry Accepted: 07/21/2007
Entry Last Modified: 07/20/2007

Modify/Update this entry