  


Small Chvatal Rank
Tristram Bogart(bogartmath.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 981954350 Download: [PDF] Entry Submitted: 07/20/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  