Lower bounds for Chvátal-Gomory style operators

Sebastian Pokutta(sebastian.pokuttamath.uni-erlangen.de)

Abstract: 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.

Keywords: cutting planes, integer programming, Chvátal-Gomory closure, rank lower bounds

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation:

Download: [PDF]

Entry Submitted: 09/05/2011
Entry Accepted: 09/05/2011
Entry Last Modified: 09/05/2011

Modify/Update this entry