×

zbMATH — the first resource for mathematics

A heuristic to generate rank-1 GMI cuts. (English) Zbl 1208.90120
Summary: Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of a MIP. In this paper, we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that, for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank-1 mixed-integer rounding cuts. Further, we use our heuristic to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T., Kock T., Martin A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 361–372 (2006) · Zbl 1133.90300 · doi:10.1016/j.orl.2005.07.009
[2] Andersen K., Cornuéjols G., Li Y.: Reduce-and-split cuts: improving the performance of mixed integer gomory cuts. Manage. Sci. 51, 1720–1732 (2005) · Zbl 1232.90310 · doi:10.1287/mnsc.1050.0382
[3] Applegate, D., Cook, W., Dash, S., Mevenkamp, M.: QSopt linear programming solver. http://www.isye.gatech.edu/\(\sim\)wcook/qsopt (2004)
[4] Balas E., Bonami P.: Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Program. Comput. 1, 165–200 (2010) · Zbl 1180.90206 · doi:10.1007/s12532-009-0006-4
[5] Balas E., Ceria S., Cornuejols G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[6] Balas E., Ceria S., Cornuejols G., Natraj N.: Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996) · Zbl 0865.90098 · doi:10.1016/0167-6377(96)00007-7
[7] Balas E., Perregaard M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0–1 programming. Math. Program. 94, 221–245 (2003) · Zbl 1030.90068 · doi:10.1007/s10107-002-0317-y
[8] Balas E., Saxena A.: Optimizing over the split closure. Math. Program. 113, 219–240 (2008) · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5
[9] Bonami, P.: CglLandP. http://project.coin-or.org/Cgl/wiki/CglLandP
[10] Bonami P., Minoux M.: Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation. Discret. Optim. 2, 288–307 (2005) · Zbl 1172.90450 · doi:10.1016/j.disopt.2005.08.006
[11] Bixby, R., Gu, Z., Rothberg, E., Wunderling, R.: The sharpest cut: the impact of Manfred Padberg and his work, chap. 18 (mixed-integer programming: a progress report), pp. 309–323. MPS-SIAM Series on Optimization (2004)
[12] Bixby R.E., Ceria S., McZeal C.M., Savelsbergh M.W.P.: An updated mixed integer programming library: Miplib 3.0. Optima 58, 12–15 (1998)
[13] Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mip: theory and practice–closing the gap. In: System modelling and optimization, pp. 19–50 (1999) · Zbl 0986.90025
[14] Bussieck M.R., Ferris M.C., Meeraus A.: Grid-enabled optimization with GAMS. INFORMS J. Comput. 21(3), 349–362 (2009) · Zbl 1243.90255 · doi:10.1287/ijoc.1090.0340
[15] Caprara A., Letchford A.: On the separation of split cuts and related inequalities. Math. Program. 94, 279–294 (2003) · Zbl 1030.90095 · doi:10.1007/s10107-002-0320-3
[16] Ceria, S., Cornuéjols, G., Dawande, M.: Combining and strengthening Gomory cuts. In: Balas, E., Clausen, J. (eds) Proceedings of IPCO 1995. Lect. Notes Comput. Sci. 920, 438–451 (1995)
[17] COIN-OR, The computational infrastructure for operations research project. http://www.coin-or.org
[18] Cook W., Dash S., Goycoolea M., Fukasawa R.: Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21, 641–649 (2009) · Zbl 1243.90135 · doi:10.1287/ijoc.1090.0324
[19] Cornuéjols G., Li Y.: Elementary closures for integer programs. Oper. Res. Lett. 28, 1–8 (2001) · Zbl 1108.90326 · doi:10.1016/S0167-6377(00)00067-5
[20] Dash S., Günlük O.: On the strength of Gomory mixed-integer cuts as group cuts. Math. Program. 115, 387–407 (2008) · Zbl 1209.90277 · doi:10.1007/s10107-007-0179-4
[21] Dash S., Goycoolea M., Günlük O.: Two-step mir inequalities for mixed-integer programs. INFORMS J. Comput. 22, 236–249 (2010) · Zbl 1243.90146 · doi:10.1287/ijoc.1090.0337
[22] Dash S., Günlük O., Lodi A.: MIR closures of polyhedral sets. Math. Program. 121(1), 33–60 (2010) · Zbl 1184.90107 · doi:10.1007/s10107-008-0225-x
[23] Edmonds J.: Matroids and the greedy algorithm. Math. Program. 1(1), 127–136 (1971) · Zbl 0253.90027 · doi:10.1007/BF01584082
[24] Fischetti M., Lodi A.: Optimizing over the first Chvátal closure. Math. Program. B 110(1), 3–20 (2007) · Zbl 1192.90125 · doi:10.1007/s10107-006-0054-8
[25] Fischetti M., Saturni C.: Mixed integer cuts from cyclic groups. Math. Program. 109, 27–53 (2007) · Zbl 1278.90274 · doi:10.1007/s10107-006-0726-4
[26] Fukasawa, R., Goycoolea, M.: On the exact separation of mixed-integer knapsack cuts. In: Fischetti, M., Williamson, D.P. (eds) Proceedings of IPCO 2007. Lect. Notes Comput. Sci. 4513, 225–239 (2007) · Zbl 1136.90418
[27] Geoffrion A.M., Graves G.W.: Multicommodity distribution system design by Benders decomposition. Manage. Sci. 20, 822–844 (1974) · Zbl 0304.90122 · doi:10.1287/mnsc.20.5.822
[28] Gomory, R.E.: An algorithm for the mixed integer problem. RM-2597, The Rand Corporation (1960)
[29] Liebchen, C., Moehring, R.H.: Information on the MIPLIB’s timetab-instances. Technical Report 2003/49, Department of Mathematics, Technical University Berlin (2003)
[30] Marchand H., Wolsey L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001) · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211
[31] Nemhauser G.L., Wolsey L.A.: Integer and combinatorial optimization. Wiley, New York (1988) · Zbl 0652.90067
[32] Margot F.: Testing cut generators for mixed-integer linear programming. Math. Program. Comput. 1, 69–95 (2009) · Zbl 1171.90478 · doi:10.1007/s12532-009-0003-7
[33] Markowitz H.M.: The elimination from of inverse and its applications to linear programming. Manage. Sci. 3, 255–269 (1957) · Zbl 0995.90592 · doi:10.1287/mnsc.3.3.255
[34] Mittelmann, H.: MIQPlib. http://plato.asu.edu/ftp/miqp/
[35] Pinar A., Chow E., Pothen A.: Combinatorial algorithms for computing column space bases that have sparse inverses. Electron. Trans. Numer. Anal. 22, 122–145 (2006) · Zbl 1112.65040
[36] Suhl U.H., Suhl L.M.: Computing sparse LU factorizations for large-scale linear programming bases. ORSA J. Comput. 2(4), 325–335 (1990) · Zbl 0755.90059
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.