## Abstract

Let S ⊂ {0; 1}n and R be any polytope contained in [0; 1]n with R ⊂ {0; 1}n = S. We prove that R has bounded Chvátal-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 conv^{1}S°. Let H[S] denote the subgraph of the n-cube induced by the vertices not in S. We prove that if H[S] does not contain a subdivision of a large complete graph, then 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 H[S]. 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éjols and Lee [Cornuéjols G, Lee D (2016) On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combinatorial Optim., IPCO '16 (Springer International, Cham, Switzerland), 300-311], who proved that the CG-rank is bounded by a constant if the treewidth of H[S] is at most 2.

Original language | English |
---|---|

Pages (from-to) | 718-725 |

Number of pages | 8 |

Journal | Mathematics of Operations Research |

Volume | 43 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1 Aug 2018 |

Externally published | Yes |

## Keywords

- Cutting-planes
- Graphs
- Integer programming
- Polyhedra