Mathematics – Optimization and Control
Scientific paper
2007-05-08
Mathematics
Optimization and Control
24 pages, 3 figures, v3. Major revision: additional author, new application to stable-set polytopes, reorganization of section
Scientific paper
We propose a variant of the Chvatal-Gomory procedure that will produce a sufficient set of facet normals for the integer hulls of all polyhedra {xx : Ax <= b} as b varies. The number of steps needed is called the small Chvatal rank (SCR) of A. We characterize matrices for which SCR is zero via the notion of supernormality which generalizes unimodularity. SCR is studied in the context of the stable set problem in a graph, and we show that many of the well-known facet normals of the stable set polytope appear in at most two rounds of our procedure. Our results reveal a uniform hypercyclic structure behind the normals of many complicated facet inequalities in the literature for the stable set polytope. Lower bounds for SCR are derived both in general and for polytopes in the unit cube.
Bogart Tristram
Raymond Annie
Thomas Rekha R.
No associations
LandOfFree
Small Chvatal rank does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Small Chvatal rank, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Chvatal rank will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-153235