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.

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