Optimization Online


On the polyhedrality of cross and quadrilateral closures

oktay gunluk (gunluk***at***us.ibm.com)
sanjeeb dash (sanjeebd***at***us.ibm.com)
diego moran (dmoran***at***gatech.edu)

Abstract: 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 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, Dey and Gunluk (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).

Keywords: Cutting planes, cross cuts, quadrilateral cuts

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: IBM Research Report

Download: [PDF]

Entry Submitted: 12/09/2014
Entry Accepted: 12/09/2014
Entry Last Modified: 01/19/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society