论文标题
两半空间封闭
Two-halfspace closure
论文作者
论文摘要
我们为纯整数程序定义了一个新的切割平面闭合，称为两半空间闭合。这是众所周知的Chvátal-Gomory闭合的自然概括。我们证明了两个半空间的闭合是多面体的。我们还研究了任何有效不平等的相应$ 2 $ -HALFPSACE等级，并表明它最多是不平等的分裂等级。此外，虽然拆分等级可能严格大于两个半空间等级，但分级排名最多是两半空间等级的两倍。我们分析的关键步骤表明，对于任何固定的$ k \ geq 2 $，可以通过考虑所有$ k $ diper（理性）预测的所有$ k $数（理性）预测来获得理性多面体的分裂封闭。该结果可能具有独立的利益。
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 Chvátal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corresponding $2$-halfpsace 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\geq 2$. This result may be of independent interest.
