Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank

DOI10.1287/MOOR.2017.0880MaRDI QIDQ5219666zbMATH OpenOpenAlexFDO

Authors Yohann Benchetrit, Samuel Fiorini, Tony Huynh, Stefan Weltge

Publication date 12 March 2020

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06593, https://dipot.ulb.ac.be/dspace/bitstream/2013/264087/3/1611.06593.pdf

zbMATH Keywords

cutting-planesgraphsinteger programmingpolyhedra

Mathematics Subject Classification ID

Integer programming (90C10) Polynomial optimization (90C23) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Abstract: Let $Ssubseteq{0,1}^n$ and $R$ be any polytope contained in $[0,1{]}^n$ with $Rcap{0,1}^n=S$. We prove that $R$ has bounded Chv'atal-Gomory rank (CG-rank) provided that $S$ has bounded notch and bounded gap, where the notch is the minimum integer $p$ such that all $p$-dimensional faces of the $0/1$-cube have a nonempty intersection with $S$, and the gap is a measure of the size of the facet coefficients of $mathsfconv(S)$. Let $$ denote the subgraph of the $n$-cube induced by the vertices not in $S$. We prove that if $$ does not contain a subdivision of a large complete graph, then both the notch and the gap are bounded. By our main result, this implies that the CG-rank of $R$ is bounded as a function of the treewidth of $$. We also prove that if $S$ has notch $3$, then the CG-rank of $R$ is always bounded. Both results generalize a recent theorem of Cornu'ejols and Lee, who proved that the CG-rank is bounded by a constant if the treewidth of $$ is at most $2$.

Recommendations

• scientific article; zbMATH DE number 1342126
• On the Chvátal rank of polytopes in the 0/1 cube
• 0/1 polytopes with quadratic Chvátal rank
• Bounds on the Chvatal rank of polytopes in the 0/1-cube
• On the rank of mixed 0,1 polyhedra.

Cites work

• 0/1 polytopes with quadratic Chvátal rank
• Bounds on the Chvatal rank of polytopes in the 0/1-cube
• Edmonds polytopes and a hierarchy of combinatorial problems
• Facet generating techniques
• Graph theory
• Improving integrality gaps via Chvátal-Gomory rounding
• Integer Programming
• On cutting-plane proofs in combinatorial optimization
• On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank
• On the Chvátal-Gomory closure of a compact convex set
• Subset Algebra Lift Operators for 0-1 Integer Programming

Cited in

(4)

• On the Chvátal rank of polytopes in the 0/1 cube
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank
• Lower bounds for cube-ideal set-systems

This page was built for publication: Characterizing polytopes in the 0/1-cube with bounded Chvátal-Gomory rank

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