Abstract
Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better.
G. Mexi and S. Shamsi—The first two authors contributed equally to the work presented in this paper.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The branching rule is integrated in github.com/matbesancon/scip on the strongbranching_dynamiclookahead_2 branch.
- 2.
The precise subset used will be made available in the companion repository of our paper.
References
Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universitat Berlin (2007)
Achterberg, T., Berthold, T.: Hybrid branching. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 309–311. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01929-6_23
Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)
Anderson, D., Le Bodic, P., Morgan, K.: Further results on an abstract model for branching and its application to mixed integer programming. Math. Program. 190(1–2), 811–841 (2021)
Applegate, D., Bixby, R., Cook, W., Chvátal, V.: On the solution of traveling salesman problems (1998)
Bartoszyński, R., Govindarajulu, Z.: The secretary problem with interview cost. Sankhyā: Indian J. Stat. Ser. B 11–28 (1978)
Besancon, M., et al.: Distributions.jl: definition and modeling of probability distributions in the JuliaStats ecosystem. J. Stat. Softw. 98(16), 1-30 (2021). https://doi.org/10.18637/jss.v098.i16
Bestuzheva, K., et al.: Enabling research through the SCIP optimization suite 8.0. ACM Trans. Math. Softw. 49(2), 1–21 (2023)
Beyhaghi, H., Cai, L.: Pandora’s problem with nonobligatory inspection: optimal structure and a PTAS
Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib’a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114–119 (2003)
Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming Models. Springer, Cham (2014)
Dey, S.S., Dubey, Y., Molinaro, M., Shah, P.: A theoretical and computational analysis of full strong-branching. Math. Program. 1–34 (2023)
Gamrath, G., et al.: The SCIP optimization suite 7.0 (2020)
Gamrath, G., Berthold, T., Salvagnin, D.: An exploratory computational analysis of dual degeneracy in mixed-integer programming. EURO J. Comput. Optim. 8(3–4), 241–261 (2020)
Gianini, J., Samuels, S.M.: The infinite secretary problem. Ann. Probab. 4(3), 418–432 (1976)
Gleixner, A., et al.: MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Math. Program. Comput. 13(3), 443–490 (2021)
Hendel, G.: Enhancing MIP branching decisions by using the sample variance of pseudo costs. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 199–214. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18008-3_14
Koch, T., Berthold, T., Pedersen, J., Vanaret, C.: Progress in mathematical programming solvers from 2001 to 2020. EURO J. Comput. Optim. 10, 100031 (2022)
Le Bodic, P., Nemhauser, G.: An abstract model for branching and its application to mixed integer programming. Math. Program. 166(1–2), 369–405 (2017)
Lodi, A., Tramontani, A.: Performance variability in mixed-integer programming. In: Theory Driven by Influential Applications, pp. 1–12. INFORMS (2013)
Turner, M., Berthold, T., Besançon, M., Koch, T.: Branching via cutting plane selection: improving hybrid branching. arXiv preprint arXiv:2306.06050 (2023)
Vigerske, S.: MINLPLib: a library of mixed-integer and continuous nonlinear programming instances (2018). https://www.minlplib.org. Accessed Dec 2023
Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw. 33(3), 563–593 (2018)
Weitzman, M.: Optimal Search for the Best Alternative, vol. 78. Department of Energy (1978)
Acknowledgements
Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M14ZAM, 05M20ZBM). We thank Nicolas Gast and Bruno Gaujal for discussions on online decision-making including the Pandora’s box problem.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Mexi, G., Shamsi, S., Besançon, M., Le Bodic, P. (2024). Probabilistic Lookahead Strong Branching via a Stochastic Abstract Branching Model. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)