面向混合整数线性规划问题的智能分支定界算法综述

doi:10.15960/j.cnki.issn.1007-6093.2026.02.019

摘要/Abstract

摘要： 混合整数线性规划(mixed integer linear programming,MILP)问题遍布现实世界的各个领域。精确求解混合整数线性规划问题属于NP-hard问题,目前先进的规划问题求解器一般以分支定界法(branch and bound,B&B)作为核心框架。但分支定界法的固有性质导致其在执行过程中的一个错误决策可能会使分支定界树膨胀,降低搜索效率。如此复杂且数据丰富的环境使得利用机器学习技术改进分支定界算法成为可能。因此,将数据驱动的机器学习方法与分支定界算法相结合从而改进其决策过程受到越来越多的重视。本文首先介绍分支定界算法,并就其中影响性能的决策过程进行分析。之后,主要从基于行为克隆(behavioral cloning)的模仿已存在的专家策略的深度学习方法以及基于发现新策略思想的强化学习(reinforcement learning,RL)方法两方面着重综述了近年来关于将机器学习方法集成到分支定界算法中的研究工作。最后,我们讨论了未来关于结合机器学习与分支定界算法可能存在的方向以及挑战。

关键词: 混合整数线性规划, 精确算法, 分支定界, 深度学习, 强化学习

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

中图分类号:

O221.2

张雪峰, 彭潇, 陈良育, 杨争峰, 曾振柄. 面向混合整数线性规划问题的智能分支定界算法综述[J]. 运筹学学报（中英文）, 2026, 30(2): 237-270.

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.

参考文献

[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.