×

zbMATH — the first resource for mathematics

MIR closures of polyhedral sets. (English) Zbl 1184.90107
Math. Program. 121, No. 1 (A), 33-60 (2010); erratum ibid. 123, No. 2 (A), 485-486 (2010).
Summary: 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 W. J. Cook et al. [Math. Program., Ser. A 47, No. 2, 155–174 (1990; Zbl 0711.90057)] 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.

MSC:
90C10 Integer programming
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
Cgllandp; MIPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen K., Cornuejols G. and Li Y. (2005). Split closure and intersection cuts. Math. Program. Ser. A 102: 457–493 · Zbl 1066.90070 · doi:10.1007/s10107-004-0558-z
[2] Balas E. and Bonami P. (2007). New variants of lift-and-project cut generation from the LP tableau: open source implementation and testing. In: Fischetti, M. and Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513, pp 89–103. Springer, Berlin · Zbl 1136.90399
[3] Balas E. (1979). Disjunctive programming. Ann. Discret. Math. 5: 3–51 · Zbl 0409.90061 · doi:10.1016/S0167-5060(08)70342-X
[4] Balas E., Ceria S. and Cornuéjols G. (1996). Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42: 1229–1246 · Zbl 0880.90105 · doi:10.1287/mnsc.42.9.1229
[5] Balas E., Ceria S., Cornuéjols G. and Natraj G. (1996). Gomory cuts revisited. Operat. Res. Lett. 19: 1–9 · Zbl 0865.90098 · doi:10.1016/0167-6377(96)00007-7
[6] Balas E. and Perregaard M. (2003). A precise correspondence between lift-and-project cuts, simple disjunctive cuts and mixed integer Gomory cuts for 0-1 programming. Math. Program. Ser. B 94: 221–245 · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y
[7] Balas E. and Saxena A. (2008). Optimizing over the split closure. Math. Program. Ser. A 113: 219–240 · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5
[8] Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: An updated mixed integer programming library: MIPLIB 3.0
[9] CglLandP: https://projects.coin-or.org/Cgl/wiki/CglLandP
[10] Bonami P. and Cornuéjols G. (2008). A note on the MIR closure. Operat. Res. Lett. 36: 4–6 · Zbl 1161.90446 · doi:10.1016/j.orl.2007.03.011
[11] Bonami P., Cornuéjols G., Dash S., Fischetti M. and Lodi A. (2008). Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Program. Ser. A 113: 241–257 · Zbl 1135.90031 · doi:10.1007/s10107-006-0051-y
[12] Bonami P. and Minoux M. (2005). Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation. Discret. Optim. 2: 288–307 · Zbl 1172.90450 · doi:10.1016/j.disopt.2005.08.006
[13] Caprara A. and Letchford A. (2003). On the separation of split cuts and related inequalities. Math. Program. Ser. B 94: 279–294 · Zbl 1030.90095 · doi:10.1007/s10107-002-0320-3
[14] Chvátal V. (1973). Edmonds polytopes and a hierarchy of combinatorial problems. Discret. Math. 4: 305–337 · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2
[15] Cook W.J., Kannan R. and Schrijver A. (1990). Chvátal closures for mixed integer programming problems. Math. Program. Ser. A 47: 155–174 · Zbl 0711.90057 · doi:10.1007/BF01580858
[16] Cornuéjols G. (2008). Valid Inequalities for Mixed Integer Linear Programs. Math. Program. Ser. B 112: 3–44 · Zbl 1278.90266 · doi:10.1007/s10107-006-0086-0
[17] Cornuéjols G. and Li Y. (2001). Elementary closures for integer programs. Operat. Res. Lett. 28: 1–8 · Zbl 1108.90326 · doi:10.1016/S0167-6377(00)00067-5
[18] Cornuéjols G. and Li Y. (2001). On the Rank of Mixed 0,1 Polyhedra. Math. Program. Ser. A 91: 391–397 · Zbl 1049.90040
[19] Danna E., Rothberg E. and Le Paper C. (2005). Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. Ser. A 102: 71–90 · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7
[20] Dash, S., Günlük, O., Goycoolea, M.: Two step MIR inequalities for mixed-integer programs. IBM Research Report 23791 (2005) · Zbl 1243.90146
[21] Eisenbrand F. (1999). On the membership problem for the elementary closure of a polyhedron. Combinatorica 19: 297–300 · Zbl 0947.90071 · doi:10.1007/s004930050057
[22] Gomory, R.E.: An algorithm for the mixed integer problem, RM-2597, The Rand Corporation (1960)
[23] Fischetti M. and Lodi A. (2007). Optimizing over the first Chvátal closure. Math. Program. Ser. B 110: 3–20 · Zbl 1192.90125 · doi:10.1007/s10107-006-0054-8
[24] Marchand H. and Wolsey L.A. (2001). Aggregation and Mixed Integer Rounding to solve MIPs. Operat. Res. 49: 363–371 · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211
[25] Nemhauser G. and Wolsey L.A. (1990). A recursive procedure to generate all cuts for 0-1 mixed integer programs. Math. Program. Ser. A 46: 379–390 · Zbl 0735.90049 · doi:10.1007/BF01585752
[26] Nemhauser G. and Wolsey L.A. (1988). Integer and Combinatorial Optimization. Wiley, New York · Zbl 0652.90067
[27] Vielma J.P. (2007). A Constructive Characterization of the Split Closure of a Mixed Integer Linear Program. Operat. Res. Lett. 35: 29–35 · Zbl 1278.90277 · doi:10.1016/j.orl.2005.12.005
[28] Wolsey L.A. (1998). Integer Programming. Wiley, New York · Zbl 0930.90072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.