On the convergence of the affine hull of the Chvàtal-Gomory closures

DOI10.1137/120898371zbMATH Open1282.90102DBLPjournals/siamdm/AverkovCPSF13arXiv1210.6280OpenAlexW2122062020WikidataQ57568114 ScholiaQ57568114MaRDI QIDQ2870517FDOQ2870517

Authors: Gennadiy Averkov, Michele Conforti, Alberto Del Pia, Marco Di Summa, Yuri Faenza 

Publication date: 21 January 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Given an integral polyhedron P and a rational polyhedron Q living in the same n-dimensional space and containing the same integer points as P, we investigate how many iterations of the Chv'atal-Gomory closure operator have to be performed on Q to obtain a polyhedron contained in the affine hull of P. We show that if P contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on n. On the other hand, we prove that if P is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

Full work available at URL: https://arxiv.org/abs/1210.6280

Recommendations

• On the Chvátal-Gomory closure of a compact convex set
• On the Chvátal-Gomory closure of a compact convex set
• On a generalization of the Chvátal-Gomory closure
• On a generalization of the Chvátal-Gomory closure
• The Chvátal-Gomory closure of a strictly convex body
• A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set
• When the Gomory-chvátal closure coincides with the integer hull
• Chudnovsky's conjecture and the stable Harbourne-Huneke containment
• On convergence of closed convex sets
• Affine diameters and chords of convex compacta

zbMATH Keywords

cutting planeaffine hullintegral polyhedronChvàtal rankChvàtal-Gomory closure

Mathematics Subject Classification ID

Integer programming (90C10) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Cited In (3)

• Complexity of linear relaxations in integer programming
• Local optimality of Zaks-Perles-Wills simplices
• Reverse split rank

This page was built for publication: On the convergence of the affine hull of the Chvàtal-Gomory closures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870517)