Publication:3453572

DOI10.1137/140959882zbMath1335.90059arXiv1211.0388OpenAlexW2567811846WikidataQ57568093 ScholiaQ57568093MaRDI QIDQ3453572

Yuri Faenza, Marco Di Summa, Alberto Del Pia, Michele Conforti, Roland Grappe

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Abstract: We introduce the reverse Chv'atal-Gomory rank r*(P) of an integral polyhedron P, defined as the supremum of the Chv'atal-Gomory ranks of all rational polyhedra whose integer hull is P. A well-known example in dimension two shows that there exist integral polytopes P with r*(P) equal to infinity. We provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite.

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

zbMATH Keywords

cutting planeChvátal rankintegral polyhedronChvátal-Gomory closure

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (7)

Largest integral simplices with one interior integral point: solution of Hensley's conjecture and related results ⋮ Theoretical challenges towards cutting-plane selection ⋮ Reverse split rank ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Aggregation-based cutting-planes for packing and covering integer programs ⋮ Local optimality of Zaks-Perles-Wills simplices ⋮ Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank

This page was built for publication: Reverse Chvátal--Gomory Rank