×

zbMATH — the first resource for mathematics

Split cuts from sparse disjunctions. (English) Zbl 1441.90099
Summary: Split cuts are arguably the most effective class of cutting planes within a branch-and-cut framework for solving general Mixed-Integer Programs (MIP). Sparsity, on the other hand, is a common characteristic of MIP problems, and it is an important part of why the simplex method works so well inside branch-and-cut. In this work, we evaluate the strength of split cuts that exploit sparsity. In particular, we show that restricting ourselves to sparse disjunctions – and furthermore, ones that have small disjunctive coefficients – still leads to a significant portion of the total gap closed with arbitrary split cuts. We also show how to exploit sparsity structure that is implicit in the MIP formulation to produce splits that are sparse yet still effective. Our results indicate that one possibility to produce good split cuts is to try and exploit such structure.
MSC:
90C11 Mixed integer programming
Software:
GCG; MIPLIB; MIPLIB2003
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Oper. Res. Lett., 34, 4, 361-372 (2006) · Zbl 1133.90300
[2] Andersen, K.; Weismantel, R.; Eisenbrand, F.; Shepherd, FB, Zero-coefficient cuts, Integer Programming and Combinatorial Optimization, 57-70 (2010), Berlin: Springer, Berlin · Zbl 1285.90015
[3] Aykanat, C.; Pinar, A.; Çatalyürek, U., Permuting sparse rectangular matrices into block-diagonal form, SIAM J. Sci. Comput., 25, 6, 1860-1879 (2004) · Zbl 1070.65027
[4] Balas, E.; Ceria, S.; Cornuéjols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. Program., 58, 1-3, 295-324 (1993) · Zbl 0796.90041
[5] Balas, E.; Ceria, S.; Cornuéjols, G., Mixed 0-1 programming by lift-and-project in a branch-and-cut framework, Manag. Sci., 42, 9, 1229-1246 (1996) · Zbl 0880.90105
[6] Balas, E.; Saxena, A., Optimizing over the split closure, Math. Program., 113, 2, 219-240 (2008) · Zbl 1135.90030
[7] Bastubbe, M., Lübbecke, M.E., Witt, J.T.: A computational investigation on the strength of Dantzig-Wolfe reformulations. In: D’Angelo, G. (ed.) 17th International Symposium on Experimental Algorithms (SEA 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 103, pp. 11:1-11:12. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). 10.4230/LIPIcs.SEA.2018.11. http://drops.dagstuhl.de/opus/volltexte/2018/8946
[8] Basu, A.; Bonami, P.; Cornuéjols, G.; Margot, F., On the relative strength of split, triangle and quadrilateral cuts, Math. Program., 126, 2, 281-314 (2011) · Zbl 1206.90103
[9] Bergner, M.; Caprara, A.; Ceselli, A.; Furini, F.; Lübbecke, ME; Malaguti, E.; Traversi, E., Automatic Dantzig-Wolfe reformulation of mixed integer programs, Math. Program., 149, 1, 391-424 (2015) · Zbl 1307.90114
[10] Bixby, R.E.: A brief history of linear and mixed-integer programming computation. Documenta Mathematica, 107-121 (2012) · Zbl 1270.90003
[11] Bixby, RE; Ceria, S.; McZeal, CM; Savelsbergh, MWP, An updated mixed integer programming library: MIPLIB 3.0, Optima, 58, 12-15 (1998)
[12] Bixby, RE; Rothberg, E., Progress in computational mixed integer programming: a look back from the other side of the tipping point, Ann. Oper. Res., 149, 2, 37-41 (2007) · Zbl 1213.90011
[13] Bonami, P., On optimizing over lift-and-project closures, Math. Program. Comput., 4, 2, 151-179 (2012) · Zbl 1275.90042
[14] Bonami, P.; Cornuéjols, G.; Dash, S.; Fischetti, M.; Lodi, A., Projected Chvátal-Gomory cuts for mixed integer linear programs, Math. Program., 113, 2, 241-257 (2008) · Zbl 1135.90031
[15] Caprara, A.; Letchford, AN, On the separation of split cuts and related inequalities, Math. Program., 94, 2, 279-294 (2003) · Zbl 1030.90095
[16] Center, I.K.: Deterministic time limit. https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.cplex.help/CPLEX/Parameters/topics/DetTiLim.html. Accessed 18 Jan 2019
[17] Cook, WJ; Kannan, R.; Schrijver, A., Chvátal closures for mixed integer programs, Math. Program., 47, 155-174 (1990) · Zbl 0711.90057
[18] Cornuéjols, G.; Nannicini, G., Practical strategies for generating rank-1 split cuts in mixed-integer linear programming, Math. Program. Comput, 3, 4, 281-318 (2011) · Zbl 1276.90040
[19] Dash, S.; Günlük, O.; Lodi, A., MIR closures of polyhedral sets, Math. Program., 121, 1, 33-60 (2010) · Zbl 1184.90107
[20] Dey, SS; Molinaro, M.; Wang, Q., Approximating polyhedra with sparse inequalities, Math. Program., 154, 1, 329-352 (2015) · Zbl 1327.90134
[21] Dey, SS; Molinaro, M.; Wang, Q., Analysis of sparse cutting planes for sparse MILPs with applications to stochastic MILPs, Math. Oper. Res., 43, 1, 304-332 (2018) · Zbl 1432.90090
[22] Fischetti, M.; Lodi, A., Optimizing over the first Chvátal closure, Math. Program., 110, 1, 3-20 (2007) · Zbl 1192.90125
[23] Fischetti, M.; Lodi, A.; Tramontani, A., On the separation of disjunctive cuts, Math. Program., 128, 1, 205-230 (2011) · Zbl 1218.90125
[24] Fischetti, M.; Salvagnin, D., A relax-and-cut framework for Gomory mixed-integer cuts, Math. Program. Comput., 3, 2, 79-102 (2011) · Zbl 1257.90057
[25] Fischetti, M.; Salvagnin, D., Approximating the split closure, INFORMS J. Comput., 25, 4, 808-819 (2013)
[26] Gamrath, G.; Lübbecke, ME; Festa, P., Experiments with a generic dantzig-wolfe decomposition for integer programs, Experimental Algorithms, 239-252 (2010), Berlin: Springer, Berlin
[27] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, RE; Danna, E.; Gamrath, G.; Gleixner, AM; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, DE; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 2, 103-163 (2011)
[28] Suhl, UH; Suhl, LM, Computing sparse LU factorizations for large-scale linear programming bases, ORSA J. Comput., 2, 4, 325-335 (1990) · Zbl 0755.90059
[29] Walter, M.; Helber, S.; Breitner, M.; Rösch, D.; Schön, C.; Graf von der Schulenburg, JM; Sibbertsen, P.; Steinbach, M.; Weber, S.; Wolter, A., Sparsity of lift-and-project cutting planes, Operations Research Proceedings 2012, 9-14 (2014), Cham: Springer, Cham
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.