|
The Chvátal rank of a polyhedron Q is the number of times one has to
iterate the derivation of the so-called Chvátal closure in order to
obtain the integer hull of Q, i.e., the polyhedron P defined as the
convex hull of the integer points in Q. This number is known to be
always finite for a fixed Q.
In this talk I will reverse this viewpoint by introducing the notion
of inverse Chvátal rank: for an integral polyhedron P, the inverse
Chvátal rank of P is the supremum of the Chvátal ranks of all
polyhedra Q whose integer hull is P. In other words, this number
describes how bad the worst linear relaxation of P is.
I will give a characterization of the integral polyhedra for which
this value is finite, and discuss bounds on the inverse Chvátal rank
for certain classes of integral polyhedra.
(This is joint work with Michele Conforti, Alberto Del Pia, Yuri
Faenza and Rolande Grappe.)
|