On some polytopes contained in the 0,1 hypercube that have a small Chvatal rank

• 成果类型: Article
• 署名作者: Cornuejols, Gerard; Lee, Dabeen
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1226-4
• 发表日期: 2018
• 页码: 467-503
• 关键词: closure; 0/1-cube

摘要

In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0, 1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of the unit hypercube. In particular, we show that when this subgraph contains no 4-cycle, the Chvatal rank is at most 3; and when it has tree width 2, the Chvatal rank is at most 4. We also give polyhedral decomposition theorems when this graph has a vertex cutset of size one or two.