Two-halfspace closure

• 成果类型: Article
• 署名作者: Basu, Amitabh; Jiang, Hongyi
• 署名单位: Johns Hopkins University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01802-x
• 发表日期: 2023
• 页码: 411-426
• 关键词: integer; polyhedrality; sets

摘要

We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chvatal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corresponding two-halfspace rank of any valid inequality and show that it is at most the split rank of the inequality. Moreover, while the split rank can be strictly larger than the two-halfspace rank, the split rank is at most twice the two-halfspace rank. A key step of our analysis shows that the split closure of a rational polyhedron can be obtained by considering the split closures of all k-dimensional (rational) projections of the polyhedron, for any fixed k >= 2. This result may be of independent interest.