{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:49:44Z","timestamp":1775026184436,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,3]]},"DOI":"10.1007\/s10107-022-01781-z","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T16:02:46Z","timestamp":1644422566000},"page":"539-559","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Lower bounds on the size of general branch-and-bound trees"],"prefix":"10.1007","volume":"198","author":[{"given":"Santanu S.","family":"Dey","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3281-1102","authenticated-orcid":false,"given":"Yatharth","family":"Dubey","sequence":"additional","affiliation":[]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"issue":"3","key":"1781_CR1","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1287\/ijoc.12.3.192.12635","volume":"12","author":"K Aardal","year":"2000","unstructured":"Aardal, K., Bixby, R.E., Hurkens, C.A., Lenstra, A.K., Smeltink, J.W.: Market split and basis reduction: towards a solution of the Cornu\u00e9jols\u2013Dawande instances. INFORMS J. Comput. 12(3), 192\u2013202 (2000)","journal-title":"INFORMS J. Comput."},{"key":"1781_CR2","volume-title":"A Course in Convexity. Graduate Studies in Mathematics","author":"AI Barvinok","year":"2002","unstructured":"Barvinok, A.I.: A Course in Convexity. Graduate Studies in Mathematics, vol. 54. American Mathematical Society, Providence (2002)"},{"key":"1781_CR3","doi-asserted-by":"crossref","unstructured":"Basu, A., Conforti, M., Di\u00a0Summa, M., Jiang, H.: Complexity of branch-and-bound and cutting planes in mixed-integer optimization\u2014ii. arXiv preprint arXiv:2011.05474 (2020)","DOI":"10.1007\/978-3-030-73879-2_27"},{"key":"1781_CR4","doi-asserted-by":"crossref","unstructured":"Basu, A., Conforti, M., Di\u00a0Summa, M., Jiang, H.: Complexity of cutting planes and branch-and-bound in mixed-integer optimization. arXiv preprint arXiv:2003.05023 (2020)","DOI":"10.1007\/978-3-030-73879-2_27"},{"key":"1781_CR5","unstructured":"Beame, P., Fleming, N., Impagliazzo, R., Kolokolova, A., Pankratov, D., Pitassi, T., Robere, R.: Stabbing planes. In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1781_CR6","doi-asserted-by":"crossref","unstructured":"Borst, S., Dadush, D., Huiberts, S., Tiwari, S.: On the integrality gap of binary integer programs with Gaussian data. arXiv preprint arXiv:2012.08346 (2020)","DOI":"10.1007\/978-3-030-73879-2_30"},{"issue":"6","key":"1781_CR7","doi-asserted-by":"publisher","first-page":"1402","DOI":"10.1287\/opre.28.6.1402","volume":"28","author":"V Chv\u00e1tal","year":"1980","unstructured":"Chv\u00e1tal, V.: Hard knapsack problems. Oper. Res. 28(6), 1402\u20131411 (1980)","journal-title":"Oper. Res."},{"key":"1781_CR8","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0024-3795(89)90476-X","volume":"114","author":"V Chv\u00e1tal","year":"1989","unstructured":"Chv\u00e1tal, V., Cook, W., Hartmann, M.: On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114, 455\u2013499 (1989)","journal-title":"Linear Algebra Appl."},{"key":"1781_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer programming, vol. 271. Springer (2014)"},{"issue":"1","key":"1781_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W Cook","year":"2001","unstructured":"Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19\u201330 (2001)","journal-title":"Math. Oper. Res."},{"key":"1781_CR11","first-page":"75","volume":"1","author":"WJ Cook","year":"1990","unstructured":"Cook, W.J., Hartmann, M.: On the complexity of branch and cut methods for the traveling salesman problem. Polyhedral Comb. 1, 75\u201382 (1990)","journal-title":"Polyhedral Comb."},{"issue":"2","key":"1781_CR12","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-009-0333-2","volume":"130","author":"G Cornu\u00e9jols","year":"2011","unstructured":"Cornu\u00e9jols, G., Liberti, L., Nannicini, G.: Improved strategies for branching on general disjunctions. Math. Program. 130(2), 225\u2013247 (2011)","journal-title":"Math. Program."},{"key":"1781_CR13","unstructured":"Dadush, D., Tiwari, S.: On the complexity of branching proofs. In: Proceedings of the 35th Computational Complexity Conference, pp. 1\u201335 (2020)"},{"issue":"3","key":"1781_CR14","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1287\/moor.1050.0151","volume":"30","author":"S Dash","year":"2005","unstructured":"Dash, S.: Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Math. Oper. Res. 30(3), 678\u2013700 (2005)","journal-title":"Math. Oper. Res."},{"key":"1781_CR15","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.disopt.2014.12.003","volume":"16","author":"S Dash","year":"2015","unstructured":"Dash, S., G\u00fcnl\u00fck, O., Molinaro, M.: On the relative strength of different generalizations of split cuts. Discrete Optim. 16, 36\u201350 (2015)","journal-title":"Discrete Optim."},{"key":"1781_CR16","doi-asserted-by":"crossref","unstructured":"Dey, S.\u00a0S., Dubey, Y., Molinaro, M.: Branch-and-bound solves random binary ips in polytime. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 579\u2013591. SIAM (2021)","DOI":"10.1137\/1.9781611976465.35"},{"key":"1781_CR17","unstructured":"Fleming, N., G\u00f6\u00f6s, 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)"},{"issue":"10","key":"1781_CR18","doi-asserted-by":"publisher","first-page":"1766","DOI":"10.1016\/j.disc.2012.01.030","volume":"312","author":"L Gottlieb","year":"2012","unstructured":"Gottlieb, L., Kontorovich, A., Mossel, E.: VC bounds on the cardinality of nearly orthogonal function classes. Discrete Math. 312(10), 1766\u20131775 (2012)","journal-title":"Discrete Math."},{"issue":"1","key":"1781_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF01580225","volume":"6","author":"RG Jeroslow","year":"1974","unstructured":"Jeroslow, R.G.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105\u2013109 (1974)","journal-title":"Math. Program."},{"key":"1781_CR20","volume-title":"Extremal Combinatorics: With Applications in Computer Science","author":"S Jukna","year":"2010","unstructured":"Jukna, S.: Extremal Combinatorics: With Applications in Computer Science, 1st edn. Springer, Berlin (2010)","edition":"1"},{"key":"1781_CR21","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28, 497\u2013520 (1960)","journal-title":"Econometrica"},{"key":"1781_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"HW Lenstra","year":"1982","unstructured":"Lenstra, H.W., Lenstra, A.K., Lov\u00e1sz, L., et al.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515\u2013534 (1982)","journal-title":"Math. Ann."},{"issue":"4","key":"1781_CR23","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"1781_CR24","doi-asserted-by":"crossref","unstructured":"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\u20131261. SIAM (2010)","DOI":"10.1137\/1.9781611973075.100"},{"key":"1781_CR25","doi-asserted-by":"publisher","first-page":"981","DOI":"10.2307\/2275583","volume":"62","author":"P Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k, P.: Lower bounds for resolution and cutting plane proofs and monotone computations. J. Symb. Log. 62, 981\u2013998 (1997)","journal-title":"J. Symb. Log."},{"key":"1781_CR26","volume-title":"Beyond the Worst-Case Analysis of Algorithms","year":"2020","unstructured":"Roughgarden, T. (ed.): Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge (2020)"},{"key":"1781_CR27","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)"},{"key":"1781_CR28","volume-title":"Integer and Combinatorial Optimization","author":"LA Wolsey","year":"1999","unstructured":"Wolsey, L.A., Nemhauser, G.L.: Integer and Combinatorial Optimization, vol. 55. Wiley, Hoboken (1999)"},{"key":"1781_CR29","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1287\/ijoc.2020.0956","volume":"33","author":"Y Yang","year":"2021","unstructured":"Yang, Y., Boland, N., Savelsbergh, M.: Multivariable branching: a 0\u20131 knapsack problem case study. INFORMS J. Comput. 33, 1259\u20131684 (2021)","journal-title":"INFORMS J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01781-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01781-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01781-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T22:19:25Z","timestamp":1677017965000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01781-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1781"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01781-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"assertion":[{"value":"24 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}