We study the mixed-integer rounding (MIR) closure of polyhedra. The MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixedinteger programming (MIP) model with linear constraints and a nonlinear 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 polyhedron is again a polyhedron. We also present some computational results with our approximate separation model.

S. Dash, O. Gunluk, A. Lodi (2007). On the MIR closure of polyhedra.

On the MIR closure of polyhedra

LODI, ANDREA
2007

Abstract

We study the mixed-integer rounding (MIR) closure of polyhedra. The MIR closure of a polyhedron is equal to its split closure and the associated separation problem is NP-hard. We describe a mixedinteger programming (MIP) model with linear constraints and a nonlinear 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 polyhedron is again a polyhedron. We also present some computational results with our approximate separation model.
2007
Integer Programming and Combinatorial Optimization
337
351
S. Dash, O. Gunluk, A. Lodi (2007). On the MIR closure of polyhedra.
S. Dash; O. Gunluk; A. Lodi
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/37341
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 15
social impact