On the polyhedrality of cross and quadrilateral closures
On the polyhedrality of cross and quadrilateral closures
复制标题
关于十字闭包和四边形闭包的多面体
DOI：
--
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
R. DiegoA.Morán
中科院分区：
文献类型：
--
作者：
S. Dash;O. Günlük;R. DiegoA.Morán
分裂割形成了混合整数规划问题的一类著名的有效不等式。Cook等人（Math Program 47：155-174，1990）证明了有理多面体P的分裂闭包也是一个多面体。本文将这一结果从单个有理多面体推广到有限个有理多面体的并。然后，我们使用这个结果来证明，横切产生的闭包是合理的多面体。交叉切割是由Dash等人（Math Program 135：221-254，2012）引入的分裂切割的推广。最后，我们证明了两行连续群松弛的四边形闭包是一个多面体，回答了Basu等人（Math Program 126：281-314，2011）中的一个公开问题。
Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook et al. (Math Program 47:155–174, 1990) showed that the split closure of a rational polyhedron P is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We then use this result to prove that cross cuts yield closures that are rational polyhedra. Cross cuts are a generalization of split cuts introduced by Dash et al. (Math Program 135:221–254, 2012). Finally, we show that the quadrilateral closure of the two-row continuous group relaxation is a polyhedron, answering an open question in Basu et al. (Math Program 126:281–314, 2011).