E-resources
Peer reviewed
Open access
-
Cornuéjols, Gérard; Patil, Vrishabh
Operations research letters, 20/May , Volume: 54Journal Article
In a classical paper, Chvátal introduced a rounding procedure for strengthening the polyhedral relaxation P of an integer program; applied recursively, the number of iterations needed to obtain the convex hull of the integer solutions in P is known as the Chvátal rank. Chvátal showed that this rank can be exponential in the input size L needed to describe P. We give a compact extended formulation of P, described by introducing binary variables, whose rank is polynomial in L.
