On the polyhedrality of cross and quadrilateral closures

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
• 署名单位: International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University; Universidad Adolfo Ibanez
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0982-x
• 发表日期: 2016
• 页码: 245-270
• 关键词: intersection cuts; cutting planes; split closure; integer; triangle

摘要

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).