Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II. (English) Zbl 1483.90083
Singh, Mohit (ed.) et al., Integer programming and combinatorial optimization. 22nd international conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12707, 383-398 (2021).
Summary: We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. In particular, we give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. To the best of our knowledge, our results are the first mathematically rigorous demonstration of the superiority of branch-and-cut over pure cutting planes and pure branch-and-bound.
For Part I, see [the authors, “Complexity of branch-and-bound and cutting planes in mixed-integer optimization”, Math. Program. A, 24 p. (2022; doi:10.1007/s10107-022-01789-5)].
For the entire collection see [Zbl 1476.90004].
For Part I, see [the authors, “Complexity of branch-and-bound and cutting planes in mixed-integer optimization”, Math. Program. A, 24 p. (2022; doi:10.1007/s10107-022-01789-5)].
For the entire collection see [Zbl 1476.90004].
MSC:
| 90C11 | Mixed integer programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
References:
| [1] | Aardal, K.; Bixby, RE; Hurkens, CA; Lenstra, AK; Smeltink, JW, Market split and basis reduction: towards a solution of the cornuéjols-dawande instances, INFORMS J. Comput., 12, 3, 192-202 (2000) · Zbl 1040.90023 · doi:10.1287/ijoc.12.3.192.12635 |
| [2] | Arora, S., Barak, B.: Computational Complexity: a Modern Approach. Cambridge University Press, Cambridge (2009) · Zbl 1193.68112 |
| [3] | Basu, A., Conforti, M., Di Summa, M., Jiang, H.: Complexity of cutting plane and branch-and-bound algorithms for mixed-integer optimization (2020). https://arxiv.org/abs/2003.05023 · Zbl 1483.90083 |
| [4] | Basu, A., Conforti, M., Di Summa, M., Jiang, H.: Complexity of cutting plane and branch-and-bound algorithms for mixed-integer optimization - II (2020). https://arxiv.org/abs/2011.05474 · Zbl 1483.90083 |
| [5] | Bixby, RE, Solving real-world linear programs: a decade and more of progress, Oper. Res., 50, 1, 3-15 (2002) · Zbl 1163.90643 · doi:10.1287/opre.50.1.3.17780 |
| [6] | Bockmayr, A.; Eisenbrand, F.; Hartmann, M.; Schulz, AS, On the Chvátal rank of polytopes in the 0/1 cube, Discrete Appl. Math., 98, 1-2, 21-27 (1999) · Zbl 0956.52013 · doi:10.1016/S0166-218X(99)00156-0 |
| [7] | Bonet, M.; Pitassi, T.; Raz, R., Lower bounds for cutting planes proofs with small coefficients, J. Symbolic Logic, 62, 3, 708-728 (1997) · Zbl 0889.03050 · doi:10.2307/2275569 |
| [8] | Buss, SR; Clote, P., Cutting planes, connectivity, and threshold logic, Arch. Math. Logic, 35, 1, 33-62 (1996) · Zbl 0841.03029 · doi:10.1007/BF01845704 |
| [9] | Chen, CP; Qi, F., Completely monotonic function associated with the gamma functions and proof of Wallis’ inequality, Tamkang J. Math., 36, 4, 303-307 (2005) · Zbl 1092.33002 · doi:10.5556/j.tkjm.36.2005.101 |
| [10] | Chvátal, V., Hard knapsack problems, Oper. Res., 28, 6, 1402-1411 (1980) · Zbl 0447.90063 · doi:10.1287/opre.28.6.1402 |
| [11] | Chvátal, V.: Cutting-plane proofs and the stability number of a graph, Report Number 84326-OR. Universität Bonn, Bonn, Institut für Ökonometrie und Operations Research (1984) |
| [12] | Chvátal, V.; Cook, WJ; Hartmann, M., On cutting-plane proofs in combinatorial optimization, Linear Algebra Appl., 114, 455-499 (1989) · Zbl 0676.90059 · doi:10.1016/0024-3795(89)90476-X |
| [13] | Clote, P.: Cutting planes and constant depth Frege proofs. In: Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science, pp. 296-307 (1992) |
| [14] | Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer programming models, Integer Programming, 45-84 (2014), Cham: Springer, Cham · Zbl 1307.90001 · doi:10.1007/978-3-319-11008-0_2 |
| [15] | Cook, WJ; Coullard, CR; Turán, G., On the complexity of cutting-plane proofs, Discrete Appl. Math., 18, 1, 25-38 (1987) · Zbl 0625.90056 · doi:10.1016/0166-218X(87)90039-4 |
| [16] | Cook, WJ; Dash, S., On the matrix-cut rank of polyhedra, Math. Oper. Res., 26, 1, 19-30 (2001) · Zbl 1073.90574 · doi:10.1287/moor.26.1.19.10593 |
| [17] | Cornuéjols, G.; Liberti, L.; Nannicini, G., Improved strategies for branching on general disjunctions, Math. Program., 130, 2, 225-247 (2011) · Zbl 1229.90104 · doi:10.1007/s10107-009-0333-2 |
| [18] | Dadush, D., Tiwari, S.: On the complexity of branching proofs. arXiv preprint arXiv:2006.04124 (2020) |
| [19] | Dash, S.; Cook, WJ; Schulz, AS, An exponential lower bound on the length of some classes of branch-and-cut proofs, Integer Programming and Combinatorial Optimization, 145-160 (2002), Heidelberg: Springer, Heidelberg · Zbl 1049.90523 · doi:10.1007/3-540-47867-1_11 |
| [20] | Dash, S., Exponential lower bounds on the lengths of some classes of branch-and-cut proofs, Math. Oper. Res., 30, 3, 678-700 (2005) · Zbl 1082.90143 · doi:10.1287/moor.1050.0151 |
| [21] | Dash, S., On the complexity of cutting-plane proofs using split cuts, Oper. Res. Lett., 38, 2, 109-114 (2010) · Zbl 1187.90204 · doi:10.1016/j.orl.2009.10.010 |
| [22] | Dey, SS; Iroume, A.; Molinaro, M., Some lower bounds on sparse outer approximations of polytopes, Oper. Res. Lett., 43, 3, 323-328 (2015) · Zbl 1408.90326 · doi:10.1016/j.orl.2015.03.007 |
| [23] | Dey, SS; Molinaro, M.; Wang, Q., Approximating polyhedra with sparse inequalities, Math. Program., 154, 1-2, 329-352 (2015) · Zbl 1327.90134 · doi:10.1007/s10107-015-0925-y |
| [24] | 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 · doi:10.1287/moor.2017.0866 |
| [25] | Eisenbrand, F.; Schulz, AS, Bounds on the Chvátal rank of polytopes in the 0/1-cube, Combinatorica, 23, 2, 245-261 (2003) · Zbl 1027.52005 · doi:10.1007/s00493-003-0020-5 |
| [26] | Eldersveld, SK; Saunders, MA, A block-LU update for large-scale linear programming, SIAM J. Matrix Anal. Appl., 13, 1, 191-201 (1992) · Zbl 0753.65050 · doi:10.1137/0613016 |
| [27] | Goerdt, A.; Börger, E.; Kleine Büning, H.; Richter, MM; Schönfeld, W., Cutting plane versus Frege proof systems, Computer Science Logic, 174-194 (1991), Heidelberg: Springer, Heidelberg · Zbl 0796.03056 · doi:10.1007/3-540-54487-9_59 |
| [28] | Goerdt, A.; Börger, E.; Jäger, G.; Kleine Büning, H.; Richter, MM, The cutting plane proof system with bounded degree of falsity, Computer Science Logic, 119-133 (1992), Heidelberg: Springer, Heidelberg · Zbl 0819.68104 · doi:10.1007/BFb0023762 |
| [29] | Grigoriev, D.; Hirsch, EA; Pasechnik, DV; Alt, H.; Ferreira, A., Complexity of semi-algebraic proofs, STACS 2002, 419-430 (2002), Heidelberg: Springer, Heidelberg · Zbl 1054.03035 · doi:10.1007/3-540-45841-7_34 |
| [30] | Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2. Springer-Verlag, Berlin (1988). doi:10.1007/978-3-642-78240-4 · Zbl 0634.05001 |
| [31] | Impagliazzo, R., Pitassi, T., Urquhart, A.: Upper and lower bounds for tree-like cutting planes proofs. In: Proceedings Ninth Annual IEEE Symposium on Logic in Computer Science, pp. 220-228. IEEE (1994) |
| [32] | Jeroslow, R.G.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105-109 (1974). doi:10.1007/BF01580225, doi:10.1007/BF01580225 · Zbl 0283.90035 |
| [33] | Karamanov, M.; Cornuéjols, G., Branching on general disjunctions, Math. Program., 128, 1-2, 403-436 (2011) · Zbl 1218.90128 · doi:10.1007/s10107-009-0332-3 |
| [34] | Krajíček, J., Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic, 63, 4, 1582-1596 (1998) · Zbl 0930.03081 · doi:10.2307/2586668 |
| [35] | Lodi, A.; Jünger, M.; Liebling, TM; Naddef, D.; Nemhauser, GL; Pulleyblank, WR; Reinelt, G.; Rinaldi, G.; Wolsey, LA, Mixed integer programming computation, 50 Years of Integer Programming 1958-2008, 619-645 (2010), Heidelberg: Springer, Heidelberg · Zbl 1187.90206 · doi:10.1007/978-3-540-68279-0_16 |
| [36] | Mahajan, A., Ralphs, T.K.: Experiments with branching using general disjunctions. In: Operations Research and Cyber-Infrastructure, pp. 101-118. Springer (2009). doi:10.1007/978-0-387-88843-9_6 |
| [37] | Mahmoud, H.; Chinneck, JW, Achieving MILP feasibility quickly using general disjunctions, Comput. Oper. Res., 40, 8, 2094-2102 (2013) · Zbl 1348.90491 · doi:10.1016/j.cor.2013.03.001 |
| [38] | Ostrowski, J.; Linderoth, J.; Rossi, F.; Smriglio, S.; Lodi, A.; Panconesi, A.; Rinaldi, G., Constraint orbital branching, Integer Programming and Combinatorial Optimization, 225-239 (2008), Heidelberg: Springer, Heidelberg · Zbl 1143.90361 · doi:10.1007/978-3-540-68891-4_16 |
| [39] | Owen, JH; Mehrotra, S., Experimental results on using general disjunctions in branch-and-bound for general-integer linear programs, Comput. Optim. Appl., 20, 2, 159-170 (2001) · Zbl 0983.90044 · doi:10.1023/A:1011207119557 |
| [40] | Pataki, G., Tural, M., Wong, E.B.: Basis reduction and the complexity of branch-and-bound. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1254-1261. SIAM (2010) · Zbl 1288.90131 |
| [41] | Pudlák, P., Lower bounds for resolution and cutting plane proofs and monotone computations, J. Symbolic Logic, 62, 3, 981-998 (1997) · Zbl 0945.03086 · doi:10.2307/2275583 |
| [42] | Pudlák, P.: On the complexity of the propositional calculus. London Mathematical Society Lecture Note Series, pp. 197-218 (1999) · Zbl 0939.03065 |
| [43] | Razborov, AA, On the width of semialgebraic proofs and algorithms, Math. Oper. Res., 42, 4, 1106-1134 (2017) · Zbl 1386.90128 · doi:10.1287/moor.2016.0840 |
| [44] | Reid, JK, A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases, Math. Program., 24, 1, 55-69 (1982) · Zbl 0492.90050 · doi:10.1007/BF01585094 |
| [45] | Rothvoß, T.; Sanitá, L.; Goemans, M.; Correa, J., 0/1 polytopes with quadratic Chvátal rank, Integer Programming and Combinatorial Optimization, 349-361 (2013), Heidelberg: Springer, Heidelberg · Zbl 1377.90112 · doi:10.1007/978-3-642-36694-9_30 |
| [46] | Schrijver, A., Theory of Linear and Integer Programming (1986), New York: John Wiley and Sons, New York · Zbl 0665.90063 |
| [47] | Sperner, E., Ein satz über untermengen einer endlichen menge, Math. Z., 27, 1, 544-548 (1928) · JFM 54.0090.06 · doi:10.1007/BF01171114 |
| [48] | Venderbei, R.J.: https://vanderbei.princeton.edu/tex/talks/IDA_CCR/SparsityMatters.pdf (2017) |
| [49] | Watson, GN, A note on gamma functions, Edinburgh Math. Notes, 42, 7-9 (1959) · Zbl 0103.29601 · doi:10.1017/S0950184300003207 |
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.
