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

DOI10.1137/120898371MaRDI QIDQ2870517zbMATH OpenOpenAlexDBLPWikidataFDO

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)

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

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)

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.

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

Cited in

(3)

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

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)