- | ||||
|
![]()
|
Lower bounds for Chvátal-Gomory style operators
Sebastian Pokutta(sebastian.pokutta 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 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 | |
![]() |