Two-halfspace closure
Two-halfspace closure
复制标题
两半空间闭合
DOI：
10.1007/s10107-022-01802-x
复制
发表时间：
2022
影响因子：
2.7
通讯作者：
Jiang, Hongyi
中科院分区：
文献类型：
--
作者：
Basu, Amitabh;Jiang, Hongyi
我们为纯整数规划定义了一种新的割平面闭包，称为两半空间闭包。它是著名的Chvátal-Gomory闭包的自然推广。证明了两半空间闭包是多面体的。我们还研究了任何有效的不等式对应的两半空间秩且证明了它至多是该不等式的分裂秩.此外，虽然分裂秩可严格大于两半空间秩，但分裂秩至多是两半空间秩的两倍。我们分析的一个关键步骤是，对于任何固定的情况，通过考虑多面体的所有维(有理)投影的分裂闭包，可以得到有理多面体的分裂闭包。这一结果可能具有独立的利益。
We define a new cutting plane closure for pure integer programs called thetwo-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 correspondingtwo-halfspace rankof 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 allk-dimensional (rational) projections of the polyhedron, for any fixed. This result may be of independent interest.
登录
查看更多内容
影响因子：
1.1
作者：
R. Gomory
通讯作者：
R. Gomory
影响因子：
0.6
作者：
Jean
通讯作者：
Jean
影响因子：
2.7
作者：
David E. Bell;M. Fisher
通讯作者：
M. Fisher
关于十字闭包和四边形闭包的多面体
影响因子：
2.7
作者：
S. Dash;O. Günlük;R. DiegoA.Morán
通讯作者：
R. DiegoA.Morán
DOI：
10.1137/s009753979528977x
发表时间：
1999
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Warwick Harvey
通讯作者：
Warwick Harvey