Optimization Online


Lower bounds for Chvátal-Gomory style operators

Sebastian Pokutta(sebastian.pokutta***at***math.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 )


Download: [PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society