Optimization Online


MIR Closures of Polyhedral Sets

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (gunluk***at***us.ibm.com)
Andrea Lodi (andrea.lodi***at***unibo.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

  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 Programming Society