MIR Closures of Polyhedral Sets
Sanjeeb Dash (sanjeebdus.ibm.com)
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.
Entry Submitted: 03/02/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|