MIR Closures of Polyhedral Sets

Sanjeeb Dash (sanjeebdus.ibm.com)
Oktay Gunluk (gunlukus.ibm.com)
Andrea Lodi (andrea.lodiunibo.it)

Abstract: We study the mixed-integer rounding (MIR) closures of polyhedral sets. The MIR closure of a polyhedral set is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a given mixed-integer set. We linearize the objective using additional variables to produce a linear MIP model that solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields a short proof of the result of Cook, Kannan and Schrijver (1990) that the split closure of a polyhedral set is again a polyhedron. We also present some computational results with our approximate separation model.

Keywords: mixed-integer rounding, closure, separation

Category 1: Integer Programming (Cutting Plane Approaches )

Citation: IBM Research Tech. Report.

Download: [Postscript][PDF]

Entry Submitted: 03/02/2007
Entry Accepted: 03/02/2007
Entry Last Modified: 03/02/2007

Modify/Update this entry