中文

Operations Research Transactions >

2026 , Vol. 30 >Issue 2: 237 - 270

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2026.02.019

A review of intelligent branch and bound algorithms for mixed integer linear programming problems

  • ZHANG Xuefeng ,
  • PENG Xiao ,
  • CHEN Liangyu ,
  • YANG Zhengfeng ,
  • ZENG Zhenbing
Expand
  • 1 Software Engineering Institute, East China Normal University, Shanghai 200062, China;
    2 College of Sciences, Shanghai University, Shanghai 200444, China

Received date: 2024-07-23

  Online published: 2026-06-12

Fold

Abstract

Mixed integer linear programming problems are spread across various fields in the real world. Solving mixed integer linear programming problems is an NP-hard problem. Current advanced solvers generally use the branch and bound method as the core framework for solving mixed integer linear programming problems. But the inherent exponential nature of branch and bound means that one wrong decision during its execution can double the size of the search tree and fail to improve the search process. Such a complex and data-rich environment, combined with a lack of formal understanding, makes it possible to leverage machine learning techniques to improve branch and bound algorithms. Therefore, combining data-driven machine learning methods with branch and bound algorithms to improve their decision-making processes has received increasing attention. In this article, we first introduce the branch and bound algorithm and analyze the possible decision-making process therein. Afterwards, the research work on integrating machine learning methods into branch and bound algorithms in recent years is mainly analyzed from two aspects: deep learning methods based on behavioral cloning that imitate existing expert strategies and reinforcement learning methods based on the idea of discovering new strategies. Finally, we discuss possible future directions and challenges in combining machine learning with branch and bound algorithms.

Key words： mixed integer linear programming; exact algorithm; branch-and-bound; deep learning; reinforcement learning

Cite this article

ZHANG Xuefeng , PENG Xiao , CHEN Liangyu , YANG Zhengfeng , ZENG Zhenbing . A review of intelligent branch and bound algorithms for mixed integer linear programming problems[J]. Operations Research Transactions, 2026 , 30(2) : 237 -270 . DOI: 10.15960/j.cnki.issn.1007-6093.2026.02.019

References

[1] Paschos V T. Applications of Combinatorial Optimization [M]. Hoboken: John Wiley & Sons, 2014.
[2] Katoch S, Chauhan S S, Kumar V. A review on genetic algorithm: Past, present, and future [J]. Multimedia Tools and Applications, 2021, 80(5): 8091-8126.
[3] Kirkpatrick S, Gelatt Jr C D, Vecchi M P. Optimization by simulated annealing [J]. Science, 1983, 220(4598): 671-680.
[4] Gurobi Optimization, LLC. Gurobi optimizer reference manual [EB/OL]. [2024-07-20]. https://www.gurobi.com, 2023.
[5] Ilog Ibm. IBM ILOG CPLEX V12.1: User’s manual for CPLEX [EB/OL]. [2024-07-20]. https://www.ibm.com/cplex, 2009.
[6] Achterberg T. SCIP: Solving constraint integer programs [J]. Mathematical Programming Computation, 2009, 1: 1-41.
[7] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks [C]//Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019: 15580-15592.
[8] Land A H, Doig A G. An automatic method for solving discrete programming problems [M]// Jünger M, Liebling T M, Naddef D, et al. (eds.) 50 Years of Integer Programming 1958-2008. Berlin: Springer, 2010: 105-132.
[9] Lodi A, Zarpellon G. On learning and branching: A survey [J]. Top, 2017, 25: 207-236.
[10] Gomory R E. An algorithm for the mixed integer problem [R]. RAND CORP SANTA MONICA CA, 1960 https://www.rand.org/pubs/research memoranda/RM2597.html
[11] Padberg M, Rinaldi G. A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems [J]. SIAM Review, 1991, 33(1): 60-100.
[12] 安邦, 程朋. 基于分支割平面的一类无容量限制设施选址问题求解算法 [J].运筹学学报, 2015, 19(4): 1-13.
[13] 于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法 [J].运筹学学报, 2023, 27(1): 115-126.
[14] 赵秀涛, 张斌, 张长胜.一种基于服务选取的SBS 云资源优化分配方法 [J]. 软件学报, 2015, 26(4): 867-885.
[15] Cheng C H, Nührenberg G, Ruess H. Maximum resilience of artificial neural networks [C]//Automated Technology for Verification and Analysis: 15th International Symposium, 2017: 251-268.
[16] Tjeng V, Xiao K, Tedrake R. Evaluating robustness of neural networks with mixed integer programming [EB/OL]. [2024-07-20]. arXiv:1711.07356.
[17] Paulus M B, Zarpellon G, Krause A, et al. Learning to cut by looking ahead: Cutting plane selection via imitation learning [C]//Proceedings of the 39th International Conference on Machine Learning, 2022: 17584-17600.
[18] Nair V, Bartunov S, Gimeno F, et al. Solving mixed integer programs using neural networks [EB/OL]. [2024-7-20]. arXiv:2012.13349.
[19] Huang Z, Wang K, Liu F, et al. Learning to select cuts for efficient mixed-integer programming [J]. Pattern Recognition, 2022, 123: 108353.
[20] Huang L, Chen X, Huo W, et al. Branch and bound in mixed integer linear programming problems: A survey of techniques and trends [EB/OL]. [2024-7-20] arXiv:2111.06257.
[21] Zhang J, Liu C, Li X, et al. A survey for solving mixed integer programming via machine learning [J]. Neurocomputing, 2023, 519: 205-217.
[22] Achterberg T, Wunderling R. Mixed integer programming: Analyzing 12 years of progress [M]// Junger M, Reinelt G et al. Facets of Combinatorial Optimization: Festschrift for Martin Grötschel. Berlin: Springer, 2013: 449-481.
[23] Applegate D, Bixby R, Chvátal V, et al. Finding cuts in the TSP (A preliminary report) [R]. DIMACS, 1995. https://citeseerx.ist.psu.edu/pdf/3f41c8569faa1cae3ae71af5bf07b65507bb164e
[24] Achterberg T, Koch T, Martin A. Branching rules revisited [J]. Operations Research Letters, 2005, 33(1): 42-54.
[25] Bénichou M, Gauthier J M, Girodet P, et al. Experiments in mixed-integer linear programming [J]. Mathematical Programming, 1971, 1: 76-94.
[26] Falk P G. Experiments in mixed integer linear programming in a manufacturing system [J]. Omega, 1980, 8(4): 473-484.
[27] Linderoth J T, Savelsbergh M W P. A computational study of search strategies for mixed integer programming [J]. INFORMS Journal on Computing, 1999, 11(2): 173-187.
[28] Dakin R J. A tree-search algorithm for mixed integer programming problems [J]. The Computer Journal, 1965, 8(3): 250-255.
[29] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.
[30] Alvarez A M, Louveaux Q, Wehenkel L. A machine learning-based approximation of strong branching [J]. INFORMS Journal on Computing, 2017, 29(1): 185-195.
[31] Khalil E B, Bodic P L, Song L, et al. Learning to branch in mixed integer programming [C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016: 724-731.
[32] Hansknecht C, Joormann I, Stiller S. Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem [EB/OL]. [2024-7-20]. arXiv:1805.01415.
[33] Gupta P, Gasse M, Khalil E B, et al. Hybrid models for learning to branch [C]//Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020: 18087- 18097.
[34] Zarpellon G, Jo J, Lodi A, et al. Parameterizing branch and bound search trees to learn branching policies [C]//Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021: 3931-3939.
[35] He H, Daume III H, Eisner J M. Learning to search in branch and bound algorithms [C]//Proceedings of the Advances in Neural Information Processing Systems, 2014: 3293-3301.
[36] Song J, Lanka R, Zhao A, et al. Learning to search via retrospective imitation [EB/OL]. [2024-7-20]. arXiv:1804.00846.
[37] Yilmaz K, Yorke-Smith N. A study of learning search approximation in mixed integer branch and bound: Node selection in SCIP [J]. AI, 2021, 2(2): 150-178.
[38] Hottung A, Tanaka S, Tierney K. Deep learning assisted heuristic tree search for the container pre-marshalling problem [J]. Computers & Operations Research, 2020, 113: 104781.
[39] Labassi A G, Chételat D, Lodi A. Learning to compare nodes in branch and bound with graph neural networks [C]//Proceedings of the Advances in Neural Information Processing Systems, 2022: 32000-32010.
[40] Thrun S, Littman M L. Reinforcement learning: An introduction [J]. AI Magazine, 2000, 21(1): 103-103.
[41] Sun H, Chen W, Li H, et al. Improving learning to branch via reinforcement learning [C]//Learning Meets Combinatorial Algorithms at the 34th International Conference on Neural Information Processing Systems, 2020.
[42] Etheve M, Alès Z, Bissuel C, et al. Reinforcement learning for variable selection in a branch and bound algorithm [C]//Proceedings of the 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2020: 176-185.
[43] Scavuzzo L, Chen F, Chételat D, et al. Learning to branch with tree mdps [C]//Proceedings of the Advances in Neural Information Processing Systems, 2022: 18514-18526.
[44] Qu Q, Li X, Zhou Y, et al. An improved reinforcement learning algorithm for learning to branch [EB/OL]. [2024-7-20]. arXiv:2201.06213.
[45] Tang Y, Agrawal S, Faenza Y. Reinforcement learning for integer programming: Learning to cut [C]//Proceedings of the 37th International Conference on Machine Learning, 2020: 9367- 9376.
[46] Hussein A, Gaber M M, Elyan E, et al. Imitation learning: A survey of learning methods [J]. ACM Computing Surveys, 2017, 50(2): 1-35.
[47] Marcos Alvarez A, Louveaux Q, Wehenkel L. A supervised machine learning approach to variable branching in branch and bound [EB/OL]. [2024-07-22]. https://orbi.uliege.be/handle/2268/167559.
[48] Geurts P, Ernst D, Wehenkel L. Extremely randomized trees [J]. Machine Learning, 2006, 63: 3-42.
[49] Joachims T. Training linear SVMs in linear time [C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006: 217-226.
[50] Burges C J C. From ranknet to Lambdarank to Lambdamart: An overview [R/OL]. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf.
[51] Pomerleau D A. Efficient training of artificial neural networks for autonomous navigation [J]. Neural computation, 1991, 3(1): 88-97.
[52] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers [J]. Foundations and Trends in Machine learning, 2011, 3(1): 1-122.
[53] Fischetti M, Lodi A, Zarpellon G. Learning MILP resolution outcomes before reaching timelimit [C]//Proceedings of the 16th Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2019: 275-291.
[54] Bengio Y, Lodi A, Prouvost A. Machine learning for combinatorial optimization: A methodological tour d’horizon [J]. European Journal of Operational Research, 2021, 290(2): 405-421.
[55] Salimans T, Ho J, Chen X, et al. Evolution strategies as a scalable alternative to reinforcement learning [EB/OL]. [2024-7-20]. arXiv:1703.03864.
[56] Conti E, Madhavan V, Such F P, et al. Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents [C]//Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018: 5032-5043.
[57] Van Hasselt H, Guez A, Silver D. Deep reinforcement learning with double Q-learning [C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016: 2094-2100.
[58] Ross S, Gordon G, Bagnell D. A reduction of imitation learning and structured prediction to no-regret online learning [C]//Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, 2011: 627-635.
[59] Ross S, Bagnell D. Efficient reductions for imitation learning [C]//Proceedings of the 13th International Conference on Artificial Intelligence and Statistics, 2010: 661-668.
[60] Hottung A, Tierney K. A biased random-key genetic algorithm for the container premarshalling problem [J]. Computers & Operations Research, 2016, 75: 83-102.
[61] Hochreiter S, Schmidhuber J. Long short-term memory [J]. Neural computation, 1997, 9(8): 1735-1780.
[62] Carbonneau M A, Cheplygina V, Granger E, et al. Multiple instance learning: A survey of problem characteristics and applications [J]. Pattern Recognition, 2018, 77: 329-353.
[63] 林嘉豪, 章宗长, 姜冲, 等. 基于生成对抗网络的模仿学习综述 [J]. 计算机学报, 2020, 43(2): 326- 351.
[64] Abbeel P, Ng A Y. Apprenticeship learning via inverse reinforcement learning [C]//Proceedings of the twenty-first international conference on Machine learning, 2004: 1.
[65] Leyton-Brown K, Pearson M, Shoham Y. Towards a universal test suite for combinatorial auction algorithms [C]//Proceedings of the 2nd ACM Conference on Electronic Commerce, 2000: 66-76.
[66] Balas E, Ho A. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study [M]//Combinatorial Optimization, Berlin: Springer, 1980: 37-60.
[67] Bergman D, Cire A A, Van Hoeve W J, et al. Decision Diagrams for Optimization [M]. New York: Springer, 2016.
[68] Cornuéjols G, Sridharan R, Thizy J M. A comparison of heuristics and relaxations for the capacitated plant location problem [J]. European Journal of Operational Research, 1991, 50(3): 280-297.
[69] Fukunaga A S. A branch and bound algorithm for hard multiple knapsack problems [J]. Annals of Operations Research, 2011, 184(1): 97-119.
[70] Hutter F, Hoos H H, Leyton-Brown K. Automated configuration of mixed integer programming solvers [C]//Proceedings of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2010: 186- 202.
[71] Erdos P, Rényi A. On the evolution of random graphs [J]. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, 5(1): 17-60.
[72] Bixby R E, Ceria S, McZeal C M, et al. An updated mixed integer programming library: MIPLIB 3.0[J]. Mathematical Programming, 1995, 68: 213-238.
[73] Koch T, Achterberg T, Andersen E, et al. MIPLIB 2010: Mixed integer programming library version 5[J]. Mathematical Programming Computation, 2011, 3(2): 103-163.
[74] Gleixner A, Hendel G, Gamrath G, et al. MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library [J]. Mathematical Programming Computation, 2021, 13(3): 443-490.
[75] Gomes C P, Van Hoeve W J, Sabharwal A. Connections in networks: A hybrid approach [C]//Proceedings of the 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 2008: 303-307.
[76] NeurIPS 2021 Competition. Machine learning for combinatorial optimization [EB/OL]. [2024- 04-20]. https://www.ecole.ai/2021/ml4co-competition/.
[77] Albert R, Barabási A L. Statistical mechanics of complex networks [J]. Reviews of Modern Physics, 2002, 74(1): 47.
[78] Pochet Y, Wolsey L A. Production Planning by Mixed Integer Programming [M]. New York: Springer, 2006.
[79] Tierney K, Malitsky Y. An algorithm selection benchmark of the container pre-marshalling problem [C]//Proceedings of the 9th International Conference on Learning and Intelligent Optimization, 2015: 17-22.
[80] Chmiela A, Khalil E, Gleixner A, et al. Learning to schedule heuristics in branch and bound [C]//Proceedings of the Advances in Neural Information Processing Systems, 2021: 24235- 24246.
[81] Béjar R, Cabiscol A, ManyàF, et al. Generating hard instances for MaxSAT [C]//Proceedings of the 39th International Symposium on Multiple-Valued Logic, 2009: 191-195.
[82] Ono M, Williams B C, Blackmore L. Probabilistic planning for continuous dynamic systems under bounded risk [J]. Journal of Artificial Intelligence Research, 2013, 46: 511-577.
[83] Morrison D R, Jacobson S H, Sauppe J J, et al. Branch and bound algorithms: A survey of recent advances in searching, branching, and pruning [J]. Discrete Optimization, 2016, 19: 79-102.
Options
Outlines

/

〈 〉