Lower bounds for Chvátal-Gomory style operators

Valid inequalities or cutting planes for (mixed-) integer programming problems are an essential theoretical tool for studying combinatorial properties of polyhedra. They are also of utmost importance for solving optimization problems in practice; in fact any modern solver relies on several families of cutting planes. The Chvátal-Gomory procedure, one such approach, has a peculiarity that differentiates it essentially from all other known cutting-plane operators. There exists a family of polytopes in the 0/1 cube for which more than n rounds of Chvátal-Gomory cuts are needed to derive the integral hull where n is the dimension of the polytope. All other known operators achieve this in at most n rounds. We will prove that this behavior is not an inherent weakness of the Chvátal-Gomory operator but rather a consequence of deriving new inequalities solely from a single inequality (not to confuse with single row cuts). We will first introduce a generalization of the Chvátal-Gomory closure which is significantly stronger than the classical Chvátal-Gomory procedure. We will then provide a new bounding technique for rank lower bounds for operators that essentially derive new inequalities from examining a single inequality only. A construction of a family of polytopes whose rank exceeds n follows. Contrasting these results we will show that as soon as the operator can use at least two inequalities for its derivations the rank in 0/1 cube is bounded by n from above and we will construct a new cutting-plane operator, the transient closure that combines a strengthening of lift-and-project cuts and generalized Chvátal-Gomory cuts. We obtain several rank lower bounds for specific families of polytopes in the process.

Article

Download

View PDF