A relax-and-cut framework for Gomory mixed-integer cuts. (English) Zbl 1257.90057
Summary: Gomory mixed-integer cuts (GMICs) are widely used in modern branch-and-cut codes for the solution of mixed-integer programs. Typically, GMICs are iteratively generated from the optimal basis of the current linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank-1 GMICs read from a basis of the original LP – the one before the addition of any cut. We adopt a relax-and-cut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast – yet accurate – variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cut-and-branch enumerative framework.
MSC:
| 90C11 | Mixed integer programming |
| 90C49 | Extreme-point and pivoting methods |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Achterberg T.: Scip: solving constraint integer programs. Math. Program. Comput. 1, 1–41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1 |
| [2] | Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1–12 (2006). doi: 10.1016/j.orl.2005.07.009 . http://www.zib.de/Publications/abstracts/ZR-05-28/ ; http://miplib.zib.de |
| [3] | Andreello, G., Caprara, A., Fischetti, M.: Embedding cuts in a branch and cut framework: a computational study with {0,1/2}-cuts. INFORMS J. Comput. (19), 229–238 (2007) · Zbl 1241.90181 |
| [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(2–3), 165–199 (2009) · Zbl 1180.90206 · doi:10.1007/s12532-009-0006-4 |
| [5] | Balas E., Ceria S., Cornuéjols G., Natraj N.: Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996) · Zbl 0865.90098 · doi:10.1016/0167-6377(96)00007-7 |
| [6] | Balas E., Jeroslow R.G.: Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4(4), 224–234 (1980) · Zbl 0439.90064 · doi:10.1016/0377-2217(80)90106-X |
| [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(2–3), 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(2), 219–240 (2008) · Zbl 1135.90030 · doi:10.1007/s10107-006-0049-5 |
| [9] | 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). http://www.caam.rice.edu/bixby/miplib/miplib.html |
| [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(4), 288–307 (2005) · Zbl 1172.90450 · doi:10.1016/j.disopt.2005.08.006 |
| [11] | Caprara A., Fischetti M., Toth P.: A heuristic method for the set covering problem. Oper. Res. 47(5), 730–743 (1999) · Zbl 0976.90086 · doi:10.1287/opre.47.5.730 |
| [12] | CglLandP. https://projects.coin-or.org/Cgl/wiki/CglLandP |
| [13] | COIN-OR. http://www.coin-or.org/ |
| [14] | Cornuéjols G.: Revival of the Gomory cuts in the 1990’s. Ann. Oper. Res. 149(1), 63–66 (2006) · Zbl 1213.90015 · doi:10.1007/s10479-006-0100-1 |
| [15] | Cornuéjols G.: Valid inequalities for mixed integer linear programs. Math. Program. 112(1), 3–44 (2008) · Zbl 1278.90266 · doi:10.1007/s10107-006-0086-0 |
| [16] | Cornuéjols G., Li Y.: Elementary closures for integer programs. Oper. Res. Lett. 28(1), 1–8 (2001) · Zbl 1108.90326 · doi:10.1016/S0167-6377(00)00067-5 |
| [17] | Dash S., Goycoolea M.: A heuristic to generate rank-1 GMI cuts. Math. Prog. Comp. 2(3), 231–257 (2010) · Zbl 1208.90120 · doi:10.1007/s12532-010-0018-0 |
| [18] | 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 |
| [19] | Escudero L.F., Guignard M., Malik K.: A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships. Ann. Oper. Res. 50(1), 219–237 (1994) · Zbl 0833.90068 · doi:10.1007/BF02085641 |
| [20] | Fischetti M., Lodi A.: Optimizing over the first Chvàtal closure. Math. Program. 110(1), 3–20 (2007) · Zbl 1192.90125 · doi:10.1007/s10107-006-0054-8 |
| [21] | Fischetti M., Salvagnin D.: Feasibility pump 2.0. Math. Program. Comput. 1(2–3), 201–222 (2009) · Zbl 1180.90208 · doi:10.1007/s12532-009-0007-3 |
| [22] | Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation (1960) · Zbl 0095.14502 |
| [23] | Guta, B.: Subgradient optimization methods in integer programming with an application to a radiation therapy problem. Ph.D. thesis, University of Kaiserslautern (2003) |
| [24] | Hiriart-Hurruty J.-B., Lemaréchal C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993) |
| [25] | Karzan F.K., Nemhauser G.L., Savelsbergh M.W.P.: Information-based branching schemes for binary linear mixed integer problems. Math. Program. Comput. 1(4), 249–293 (2009) · Zbl 1184.90114 · doi:10.1007/s12532-009-0009-1 |
| [26] | Lucena, A.: Steiner problems in graphs: Lagrangian optimization and cutting planes. COAL Bulletin (21), 2–8 (1982) |
| [27] | Lucena A.: Non-delayed relax-and-cut algorithms. Ann. Oper. Res. 140(1), 375–410 (2005) · Zbl 1091.90082 · doi:10.1007/s10479-005-3977-1 |
| [28] | Lucena, A.: Lagrangian relax-and-cut algorithms. In: Handbook of Optimization in Telecommunications, pp. 129–145. Springer, Berlin (2006) · Zbl 1118.90057 |
| [29] | Ralphs T.K., Kopman L., Pulleyblank W.R., Trotter L.E.: On the capacitated vehicle routing problem. Math. Program. 94(2–3), 343–359 (2003) · Zbl 1030.90131 · doi:10.1007/s10107-002-0323-0 |
| [30] | Zanette, A., Fischetti, M., Balas, E.: Lexicography and degeneracy: can a pure cutting plane algorithm work? Math. Program. 1–24 (2009) · Zbl 1229.90101 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
