Characterizing Polytopes in the 0/1-Cube with Bounded Chvatal-Gomory Rank

• 成果类型: Article
• 署名作者: Benchetrit, Yohann; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
• 署名单位: Universite Libre de Bruxelles
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0880
• 发表日期: 2018
• 页码: 718-725

摘要

Let S subset of {0, 1}(n) and R be any polytope contained in [0, 1](n) with R boolean AND {0, 1}(n) = S. We prove that R has bounded Chvatal-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(S). Let H[(S) over bar] denote the subgraph of the n-cube induced by the vertices not in S. We prove that if H[(S) over bar] 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) over bar]. 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 Cornuejols and Lee [Cornuejols G, Lee D (2016) On some polytopes contained in the 0,1 hypercube that have a small Chvatal 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) over bar] is at most 2.