  


Lower bounds for ChvátalGomory style operators
Sebastian Pokutta(sebastian.pokuttamath.unierlangen.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átalGomory procedure, one such approach, has a peculiarity that differentiates it essentially from all other known cuttingplane operators. There exists a family of polytopes in the 0/1 cube for which more than n rounds of ChvátalGomory 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átalGomory 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átalGomory closure which is significantly stronger than the classical ChvátalGomory 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 cuttingplane operator, the transient closure that combines a strengthening of liftandproject cuts and generalized ChvátalGomory cuts. We obtain several rank lower bounds for specific families of polytopes in the process. Keywords: cutting planes, integer programming, ChvátalGomory closure, rank lower bounds Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming (01 Programming ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: Download: [PDF] Entry Submitted: 09/05/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  