Abstract
We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash (International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145–160, 2002) to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by giving instances of the stable set problem where we can provably establish that CP does exponentially better than BB. We further show that if one moves away from 0/1 sets, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). We next show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up factor), for quite general families of disjunctions. This is also complemented by examples where this gap is exponential (in the size of the input data).
Similar content being viewed by others
Notes
We make the standard notational convention that the trivial intersection \(\bigcap _{i=1}^0 X_i = \mathbb {R}^n\).
References
Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2011)
Balas, E.: Facets of the knapsack polytope. Math. Program. 8(1), 146–164 (1975)
Balas, E., Ceria, S., Cornuéjols, G., Natraj, N.R.: Gomory cuts revisited. Operations Res. Lett. 19(1), 1–9 (1996)
Banaszczyk, W.: Inequalities for convex bodies and polar reciprocal lattices in \({R}^n\) II: application of K-convexity. Discrete Comput. Geom. 16(3), 305–311 (1996)
Banaszczyk, W., Litvak, A.E., Pajor, A., Szarek, S.J.: The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Math. Operations Res. 24(3), 728–750 (1999). https://doi.org/10.1287/moor.24.3.728
Barvinok, A.: A Course in Convexity, vol. 54. American Mathematical Society, Providence, Rhode Island (2002)
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. To appear in Combinatorica
Basu, A., Conforti, M., Di Summa, M., Jiang, H.: Split cuts in the plane. SIAM J. Optim. 31(1), 331–347 (2021)
Beame, P., Fleming, N., Impagliazzo, R., Kolokolova, A., Pankratov, D., Pitassi, T., Robere, R.: Stabbing Planes. In: A.R. Karlin (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 94, pp. 10:1–10:20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https://doi.org/10.4230/LIPIcs.ITCS.2018.10. http://drops.dagstuhl.de/opus/volltexte/2018/8341
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed integer programming: A progress report. In: The Sharpest Cut, pp. 309–325. MPS-SIAM Series on Optimization, Philadelphia, PA (2004)
Bockmayr, A., Eisenbrand, F., Hartmann, M., Schulz, A.S.: On the Chvátal rank of polytopes in the 0/1 cube. Discrete Appl. Math. 98(1–2), 21–27 (1999)
Bonet, M., Pitassi, T., Raz, R.: Lower bounds for cutting planes proofs with small coefficients. J. Symbol. Logic 62(3), 708–728 (1997)
Buck, R.C.: Partition of space. Am. Math. Month. 50(9), 541–544 (1943)
Buss, S.R., Clote, P.: Cutting planes, connectivity, and threshold logic. Arch. Math. Logic 35(1), 33–62 (1996)
Chvátal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4), 305–337 (1973)
Chvátal, V.: Edmonds polytopes and weakly Hamiltonian graphs. Math. Program. 5(1), 29–40 (1973)
Chvátal, V.: On certain polytopes associated with graphs. J. Combinat. Theory Series B 18(2), 138–154 (1975)
Chvátal, V.: Hard knapsack problems. Operations Res. 28(6), 1402–1411 (1980)
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)
Chvátal, V., Cook, W.J., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114, 455–499 (1989)
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)
Conforti, M., Del Pia, A., Di Summa, M., Faenza, Y., Grappe, R.: Reverse Chvátal-Gomory rank. SIAM J. Discrete Math. 29(1), 166–181 (2015)
Cook, W.J., Coullard, C.R., Turán, G.: On the complexity of cutting-plane proofs. Discrete Appl. Math. 18(1), 25–38 (1987)
Cook, W.J., Dash, S.: On the matrix-cut rank of polyhedra. Math. Operations Res. 26(1), 19–30 (2001)
Cook, W.J., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)
Cornuéjols, G., Fonlupt, J., Naddef, D.: The traveling salesman problem on a graph and some related integer polyhedra. Math. Program. 33(1), 1–27 (1985)
Cornuéjols, G., Naddef, D., Pulleyblank, W.R.: Halin graphs and the travelling salesman problem. Math. Program. 26(3), 287–294 (1983)
Cornuéjols, G., Pulleyblank, W.: The travelling salesman polytope and \(\{\)0, 2\(\}\)-matchings. North-Holland Math. Stud. 66, 27–55 (1982)
Dadush, D., Tiwari, S.: On the complexity of branching proofs. arXiv preprint arXiv:2006.04124 (2020)
Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Operations Res. Soc. Am. 2(4), 393–410 (1954)
Dantzig, G., Fulkerson, R., Johnson, S.: On a linear-programming, combinatorial approach to the traveling-salesman problem. Operations Res. 7(1), 58–66 (1959)
Dash, S.: An exponential lower bound on the length of some classes of branch-and-cut proofs. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 145–160. Springer (2002)
Dash, S.: Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Math. Operations Res. 30(3), 678–700 (2005)
Dash, S.: On the complexity of cutting-plane proofs using split cuts. Operations Res. Lett. 38(2), 109–114 (2010)
Dash, S., Dobbs, N.B., Günlük, O., Nowicki, T.J., Świrszcz, G.M.: Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming. Math. Program. 145(1–2), 483–508 (2014)
Dey, S.S., Dubey, Y., Molinaro, M.: Branch-and-bound solves random binary packing IPs in polytime. arXiv preprint arXiv:2007.15192 (2020)
Dey, S.S., Dubey, Y., Molinaro, M.: Lower bounds on the size of general branch-and-bound trees. arXiv preprint arXiv:2103.09807 (2021)
Dey, S.S., Shah, P.: Lower bound on size of branch-and-bound trees for solving lot-sizing problem. arXiv preprint arXiv:2112.03965 (2021)
Edmonds, J.: Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bureau Standards B 69(125–130), 55–56 (1965)
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
Eisenbrand, F., Schulz, A.S.: Bounds on the Chvátal rank of polytopes in the 0/1-cube. Combinatorica 23(2), 245–261 (2003)
Fleming, N., Göös, M., Impagliazzo, R., Pitassi, T., Robere, R., Tan, L.Y., Wigderson, A.: On the power and limitations of branch and cut. arXiv preprint arXiv:2102.05019 (2021)
Goerdt, A.: Cutting plane versus frege proof systems. In: International Workshop on Computer Science Logic, pp. 174–194. Springer (1990)
Goerdt, A.: The cutting plane proof system with bounded degree of falsity. In: International Workshop on Computer Science Logic, pp. 119–133. Springer (1991)
Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64, 275–278 (1958)
Gomory, R.E.: An algorithm for the mixed integer problem. Tech. rep., DTIC Document (1960)
Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. In: Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 419–430. Springer (2002)
Grötschel, M., Padberg, M.W.: On the symmetric travelling salesman problem I: inequalities. Math. Program. 16(1), 265–280 (1979)
Grötschel, M., Padberg, M.W.: On the symmetric travelling salesman problem II: lifting theorems and facets. Math. Program. 16(1), 281–302 (1979)
Grötschel, M., Padberg, M.W.: Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization pp. 251–305 (1985)
Grötschel, M., Pulleyblank, W.R.: Clique tree inequalities and the symmetric travelling salesman problem. Math. Operations Res. 11(4), 537–569 (1986)
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)
Jeroslow, R.G.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105–109 (1974). https://doi.org/10.1007/BF01580225
Krajíček, J.: Discretely ordered modules as a first-order extension of the cutting planes proof system. J. Symbol. Logic 63(4), 1582–1596 (1998)
Krishnamoorthy, B.: Bounds on the size of branch-and-bound proofs for integer knapsacks. Operations Res. Lett. 36(1), 19–25 (2008)
Nemhauser, G.L., Trotter, L.E., Jr.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48–61 (1974)
Owen, J.H., Mehrotra, S.: A disjunctive cutting plane procedure for general mixed-integer linear programs. Math. Program. 89(3), 437–448 (2001)
Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5(1), 199–215 (1973)
Pudlák, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symbol. Logic 62(3), 981–998 (1997)
Pudlák, P.: On the complexity of the propositional calculus. London Mathematical Society Lecture Note Series pp. 197–218 (1999)
Razborov, A.A.: On the width of semialgebraic proofs and algorithms. Math. Operations Res. 42(4), 1106–1134 (2017)
Rothvoß, T., Sanità, L.: 0/1 polytopes with quadratic Chvátal rank. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 349–361. Springer (2013)
Rudelson, M.: Distances between non-symmetric convex bodies and the \({MM}^*\)-estimate. Positivity 4(2), 161–178 (2000)
Schrijver, A.: Theory of Linear and Integer Programming. John Wiley and Sons, New York (1986)
Trotter, L.E., Jr.: A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12(4), 373–388 (1975)
Wolsey, L.A.: Faces for a linear inequality in 0–1 variables. Math. Program. 8(1), 165–178 (1975)
Zaslavsky, T.: A combinatorial analysis of topological dissections. Adv. Math. 25(3), 267–285 (1977)
Acknowledgements
Daniel Dadush pointed out to us the example by Dash et al. from [35] that establishes an exponential lower bound on any BB proof based on general split disjunctions. The manuscript also benefited greatly from discussions with Aleksandr Kazachkov, Andrea Lodi and Sriram Sankaranarayanan. Part of this work was done when the first author was visiting the Centre de Recherches Mathématiques (CRM) at Université de Montréal, Canada as part of the Simons-CRM scholar-in-residence program. The visit and the research done was supported in part by funding from the Simons Foundation and the Centre de Recherches Mathématiques.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Michele Conforti and Marco Di Summa were supported by the Italian Ministry of Education, University and Research (Ministero dell’Istruzione, dell’Università e della Ricerca MIUR) grant 2015B5F27W. Amitabh Basu and Hongyi Jiang gratefully acknowledge support from the National Science Foundation (NSF) grants CMMI1452820, CCF2006587, the Office of Naval Research (ONR) grant N000141812096 and the Air Force Office of Scientific Research (AFOSR) grant FA95502010341.
Rights and permissions
About this article
Cite this article
Basu, A., Conforti, M., Di Summa, M. et al. Complexity of branch-and-bound and cutting planes in mixed-integer optimization. Math. Program. 198, 787–810 (2023). https://doi.org/10.1007/s10107-022-01789-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-022-01789-5