MIR closures of polyhedral sets

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 exactly. Using a subset of these additional variables yields an MIP model which solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields an alternative proof of the result of Cook et al. (1990) that the split closure of a polyhedral set is again a polyhedron. We also discuss a heuristic to obtain MIR cuts based on our approximate separation model, and present some computational results. © 2008 Springer-Verlag.