On the Polyhedrality of Cross and Quadrilateral Closures

Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook, Kannan and Schrijver (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 nite 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, Dey and Günlük (2012). Finally, we show that the quadrilateral closure of the two-row continuous group relaxation is a polyhedron, answering an open question in Basu, Bonami, Cornuejols and Margot (2011).

By: Sanjeeb Dash, Oktay Günlük, Diego A. Morán

Published in: Mathematical Programming , volume 160, (no 1-2), pages 245-70 in 2016

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .