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.
Citation
University of Washington Department of Mathematics Box 354350 Seattle, WA 98195-4350