{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:50:41Z","timestamp":1775026241792,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T00:00:00Z","timestamp":1688083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T00:00:00Z","timestamp":1688083200000},"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":[[2024,5]]},"DOI":"10.1007\/s10107-023-01977-x","type":"journal-article","created":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T16:02:10Z","timestamp":1688140930000},"page":"303-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A theoretical and computational analysis of full strong-branching"],"prefix":"10.1007","volume":"205","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":[]},{"given":"Prachi","family":"Shah","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,30]]},"reference":[{"key":"1977_CR1","unstructured":"Achterberg, T. Constraint integer programming. PhD Thesis (2007)"},{"issue":"1","key":"1977_CR2","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42\u201354 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1977_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1287\/ijoc.2016.0723","volume":"29","author":"A Marcos Alvarez","year":"2017","unstructured":"Marcos Alvarez, A., Louveaux, Q., Wehenkel, L.: A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1), 185\u2013195 (2017)","journal-title":"INFORMS J. Comput."},{"key":"1977_CR4","volume-title":"Finding cuts in the tsp (a preliminary report)","author":"D Applegate","year":"1995","unstructured":"Applegate, D., Bixby, R., Chv\u00e1tal, V., Cook, W.: Finding cuts in the tsp (a preliminary report). Technical report, Citeseer (1995)"},{"key":"1977_CR5","unstructured":"Balcan, M.-F., Dick, T., Sandholm, T., Vitercik, E.: Learning to branch. In International conference on machine learning, pp. 344\u2013353. PMLR (2018)"},{"key":"1977_CR6","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":"1977_CR7","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-ii. In: Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, Atlanta, GA, USA, May 19\u201321, 2021, Proceedings 22, pp. 383\u2013398. Springer (2021)","DOI":"10.1007\/978-3-030-73879-2_27"},{"issue":"1","key":"1977_CR8","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01584074","volume":"1","author":"M B\u00e9nichou","year":"1971","unstructured":"B\u00e9nichou, M., Gauthier, J.-M., Girodet, P., Hentges, G., Ribi\u00e8re, G., Vincent, O.: Experiments in mixed-integer linear programming. Math. Program. 1(1), 76\u201394 (1971)","journal-title":"Math. Program."},{"key":"1977_CR9","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization, volume\u00a06. Athena Scientific, Belmont, MA (1997)"},{"issue":"1\u20132","key":"1977_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-016-1005-7","volume":"161","author":"M Bodur","year":"2017","unstructured":"Bodur, M., Dash, S., G\u00fcnl\u00fck, O.: Cutting planes from extended lp formulations. Math. Program. 161(1\u20132), 159\u2013192 (2017)","journal-title":"Math. Program."},{"key":"1977_CR11","doi-asserted-by":"crossref","unstructured":"Borst, S., Dadush, D., Huiberts, S., Tiwari, S.: On the integrality gap of binary integer programs with gaussian data. In IPCO, pp. 427\u2013442 (2021)","DOI":"10.1007\/978-3-030-73879-2_30"},{"key":"1977_CR12","doi-asserted-by":"crossref","unstructured":"Breu, R., Burdet, C.-A.: Branch and bound experiments in zero-one programming. In: Approaches to Integer Programming, pp. 1\u201350. Springer (1974)","DOI":"10.1007\/BFb0120687"},{"issue":"6","key":"1977_CR13","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":"1977_CR14","doi-asserted-by":"crossref","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer programming, volume 271. Springer (2014)","DOI":"10.1007\/978-3-319-11008-0"},{"key":"1977_CR15","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized algorithms, volume\u00a05. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1977_CR16","unstructured":"Dadush, D., Tiwari, S.: On the complexity of branching proofs. arXiv preprint arXiv:2006.04124 (2020)"},{"issue":"3","key":"1977_CR17","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1093\/comjnl\/8.3.250","volume":"8","author":"RJ Dakin","year":"1965","unstructured":"Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250\u2013255 (1965)","journal-title":"Comput. J."},{"key":"1977_CR18","doi-asserted-by":"crossref","unstructured":"Dey, S.S., 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":"1977_CR19","doi-asserted-by":"crossref","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M.: Lower bounds on the size of general branch-and-bound trees. arXiv preprint arXiv:2103.09807 (2021)","DOI":"10.1007\/s10107-022-01781-z"},{"issue":"7","key":"1977_CR20","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1287\/mnsc.12.7.576","volume":"12","author":"NJ Driebeek","year":"1966","unstructured":"Driebeek, N.J.: An algorithm for the solution of mixed integer programming problems. Manage. Sci. 12(7), 576\u2013587 (1966)","journal-title":"Manage. Sci."},{"issue":"4","key":"1977_CR21","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1137\/0804046","volume":"4","author":"J Eckstein","year":"1994","unstructured":"Eckstein, J.: Parallel branch-and-bound algorithms for general mixed integer programming on the cm-5. SIAM J. Optim. 4(4), 794\u2013814 (1994)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"1977_CR22","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1287\/mnsc.20.5.736","volume":"20","author":"JJH Forrest","year":"1974","unstructured":"Forrest, J.J.H., Hirst, J.P.H., Tomlin, J.A.: Practical solution of large mixed integer programming problems with umpire. Manage. Sci. 20(5), 736\u2013773 (1974)","journal-title":"Manage. Sci."},{"key":"1977_CR23","unstructured":"Gasse, M., Ch\u00e9telat, D., Ferroni, N., Charlin, L., Lodi, A.: Exact combinatorial optimization with graph convolutional neural networks. arXiv preprint arXiv:1906.01629 (2019)"},{"issue":"1","key":"1977_CR24","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/BF01593767","volume":"12","author":"J-M Gauthier","year":"1977","unstructured":"Gauthier, J.-M., Ribi\u00e8re, G.: Experiments in mixed-integer linear programming using pseudo-costs. Math. Program. 12(1), 26\u201347 (1977)","journal-title":"Math. Program."},{"key":"1977_CR25","unstructured":"Gupta, P., Gasse, M., Khalil, E.B., Kumar, M.P. Lodi, A., Bengio, Y.: Hybrid models for learning to branch. arXiv preprint arXiv:2006.15212 (2020)"},{"issue":"1","key":"1977_CR26","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1287\/opre.12.1.122","volume":"12","author":"WC Healy Jr","year":"1964","unstructured":"Healy, W.C., Jr.: Multiple choice programming (a procedure for linear programming with zero-one variables). Oper. Res. 12(1), 122\u2013138 (1964)","journal-title":"Oper. Res."},{"issue":"1","key":"1977_CR27","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":"1977_CR28","doi-asserted-by":"crossref","unstructured":"Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., Dilkina, B.: Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume\u00a030 (2016)","DOI":"10.1609\/aaai.v30i1.10080"},{"key":"1977_CR29","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":"1977_CR30","first-page":"221","volume":"5","author":"AH Land","year":"1979","unstructured":"Land, A.H., Powell, S.: Computer codes for problems of integer programming. In Annals of Discrete Mathematics. Elsevier, 5, 221\u2013269 (1979)","journal-title":"Elsevier,"},{"issue":"1","key":"1977_CR31","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10107-016-1101-8","volume":"166","author":"P Le Bodic","year":"2017","unstructured":"Le Bodic, P., Nemhauser, G.: An abstract model for branching and its application to mixed integer programming. Math. Program. 166(1), 369\u2013405 (2017)","journal-title":"Math. Program."},{"issue":"2","key":"1977_CR32","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/ijoc.11.2.173","volume":"11","author":"JT Linderoth","year":"1999","unstructured":"Linderoth, J.T., Savelsbergh, M.W.P.: A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2), 173\u2013187 (1999)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"1977_CR33","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11750-017-0451-6","volume":"25","author":"A Lodi","year":"2017","unstructured":"Lodi, A., Zarpellon, G.: On learning and branching: a survey. TOP 25(2), 207\u2013236 (2017)","journal-title":"TOP"},{"issue":"1","key":"1977_CR34","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01584658","volume":"4","author":"G Mitra","year":"1973","unstructured":"Mitra, G.: Investigation of some branch and bound strategies for the solution of mixed integer linear programs. Math. Program. 4(1), 155\u2013170 (1973)","journal-title":"Math. Program."},{"key":"1977_CR35","unstructured":"Vinod, N., Sergey, B., Felix, G., Ingrid, von G., Pawel, L., Ivan, L., Brendan, O., Nicolas, S., Christian, T., Pengming, W., et\u00a0al.: Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349 (2020)"},{"issue":"1","key":"1977_CR36","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Math. Program. 6(1), 48\u201361 (1974)","journal-title":"Math. Program."},{"issue":"1","key":"1977_CR37","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975)","journal-title":"Math. Program."},{"key":"1977_CR38","volume-title":"Integer and combinatorial optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and combinatorial optimization, vol. 55. Wiley, Hoboken (1999)"},{"issue":"2","key":"1977_CR39","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10957-009-9523-6","volume":"142","author":"BK Pagnoncelli","year":"2009","unstructured":"Pagnoncelli, B.K., Ahmed, S., Shapiro, A.: Computational study of a chance constrained portfolio selection problem. J. Optim. Theory Appl. 142(2), 399\u2013416 (2009)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"1977_CR40","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01593772","volume":"12","author":"J-C Picard","year":"1977","unstructured":"Picard, J.-C., Queyranne, M.: On the integer-valued variables in the linear vertex packing problem. Math. Program. 12(1), 97\u2013101 (1977)","journal-title":"Math. Program."},{"issue":"3","key":"1977_CR41","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1287\/ijoc.2013.0582","volume":"26","author":"F Qiu","year":"2014","unstructured":"Qiu, F., Ahmed, S., Dey, S.S., Wolsey, L.A.: Covering linear programming with violations. INFORMS J. Comput. 26(3), 531\u2013546 (2014)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"1977_CR42","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10288-007-0057-1","volume":"6","author":"D Quadt","year":"2008","unstructured":"Quadt, D., Kuhn, H.: Capacitated lot-sizing with extensions. A review. 4OR 6(1), 61\u201383 (2008)","journal-title":"4OR"},{"issue":"3","key":"1977_CR43","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/3232535","volume":"62","author":"T Roughgarden","year":"2019","unstructured":"Roughgarden, T.: Beyond worst-case analysis. Commun. ACM 62(3), 88\u201396 (2019)","journal-title":"Commun. ACM"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01977-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01977-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01977-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T14:16:46Z","timestamp":1712413006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01977-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,30]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1977"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01977-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,30]]},"assertion":[{"value":"9 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}