Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

Rui Wang; Zhiming Zhou; Kaiwen Li; Tao Zhang; Ling Wang; Xin Xu; Xiangke Liao

doi:10.1109/JAS.2023.124113

Volume 11 Issue 1

Jan. 2024

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2024 > 11(1): 157-169

R. Wang, Z. Zhou, K. Li, T. Zhang, L. Wang, X. Xu, and X. Liao, “Learning to branch in combinatorial optimization with graph pointer networks,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 1, pp. 157–169, Jan. 2024. doi: 10.1109/JAS.2023.124113

Citation:

R. Wang, Z. Zhou, K. Li, T. Zhang, L. Wang, X. Xu, and X. Liao, “Learning to branch in combinatorial optimization with graph pointer networks,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 1, pp. 157–169, Jan. 2024. doi: 10.1109/JAS.2023.124113

Citation:

PDF( 1103 KB)

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

doi: 10.1109/JAS.2023.124113

Funds: This work was supported by the Open Project of Xiangjiang Laboratory (22XJ02003), Scientific Project of the National University of Defense Technology (NUDT) (ZK21-07, 23-ZZCX-JDZ-28), the National Science Fund for Outstanding Young Scholars (62122093), and the National Natural Science Foundation of China (72071205)

More Information

Author Bio:
Rui Wang (Senior Member, IEEE) received the B.S. degree in system engineering from the National University of Defense Technology (NUDT) in 2008, and the Ph.D. degree in system engineering from the University of Sheffield, UK in 2013. Currently, he is with the National University of Defense Technology. His current research interests include evolutionary computation, multiobjective optimization and the development of algorithms applicable in practice. Dr. Wang has authored more than 40 referred papers including those published in IEEE Transactions on Evolutionary Computation, IEEE Transactions on Cybernetics, and Information Sciences. He serves as an Associate Editor of the IEEE Transacions on Evolutionary Computation, Swarm and Evolutionary Computation, Expert System with Applications, etc. He is the recipients of The Operational Research Society Ph.D. Prize in 2014, of the Funds for Distinguished Young Scientists from the Natural Science Foundation of Hunan province at 2016, of the Wu Wen-Jun Artificial Intelligence Outstanding Young Scholar at 2017, of the National Science Fund for Outstanding Young Scholars at 2021

Zhiming Zhou received the B.S. and Ph.D. degrees in control science and engineering from Beijing Institute of Technology in 2015 and 2021, respectively. He is a Assistant Research Fellow with the Institute of Automation, Chinese Academy of Sciences. His research interests include reinforcement learning, optimal control and flight control and decisions making

Kaiwen Li received the B.S., M.S. and Ph.D. degrees in management science and engineering from National University of Defense Technology (NUDT), in 2016, 2018 and 2022, respectively. He is a Lecturer with the College of Systems Engineering, NUDT. His research interests include prediction technique, multiobjective optimization, reinforcement learning, data mining, and optimization methods on energy Internet

Tao Zhang received the B.S., M.S, and Ph.D. degrees in management science and engineering from National University of Defense Technology (NUDT) in 1998, 2001 and 2004, respectively. He is a Professor with the College of Systems Engineering, NUDT. His research interests include multicriteria decision making, optimal scheduling, data mining, and optimization methods on energy Internet network

Ling Wang received the B.Sc. degree in automation, and the Ph.D. degree in control theory and control engineering from Tsinghua University in 1995 and 1999, respectively. Since 1999, he has been with the Department of Automation, Tsinghua University, where he became a Full Professor in 2008. His current research interests include intelligent optimization and production scheduling. He was the recipient of the National Natural Science Fund for Distinguished Young Scholars of China, the National Natural Science Award (second place) in 2014, the Science and Technology Award of Beijing City in 2008, and the Natural Science Award (first place in 2003, and second place in 2007) nominated by the Ministry of Education of China

Xin Xu (Senior Member, IEEE) received the B.S. and the Ph.D. degrees in control science and engineering from National University of Defense Technology (NUDT) in 1996 and 2022, respectively. He is currently a Full Professor with the Institute of Unmanned Systems, College of Intelligence Science and Technology, NUDT. His research interests include intelligent control, reinforcement learning, approximate dynamic programming, machine learning, robotics, and autonomous vehicles. He received the National Science Fund for Outstanding Youth in China and the second-class National Natural Science Award of China

Xiangke Liao received the B.S. degree in computer science and technology from Tsinghua University in 1985, and the M.S. degree in computer science and technology from the National University of Defense Technology (NUDT) in 1988, both in computer science. He is currently a Professor with the College of Computer Science and Technology, NUDT. His research interests include high-performance computing systems, operating systems, and parallel and distributed computing. He is the Principle Investigator and Chief Designer of Tianhe-2 supercomputer
Corresponding author: Kaiwen Li, e-mail: likaiwen@nudt.edu.cn; Tao Zhang, e-mail: zhangtao@nudt.edu.cn
Received Date: 2023-06-14
Revised Date: 2023-08-31
Accepted Date: 2023-11-07

Available Online: 2023-12-12

Abstract

Abstract

Traditional expert-designed branching rules in branch-and-bound (B&B) are static, often failing to adapt to diverse and evolving problem instances. Crafting these rules is labor-intensive, and may not scale well with complex problems. Given the frequent need to solve varied combinatorial optimization problems, leveraging statistical learning to auto-tune B&B algorithms for specific problem classes becomes attractive. This paper proposes a graph pointer network model to learn the branch rules. Graph features, global features and historical features are designated to represent the solver state. The graph neural network processes graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch. The model is trained to imitate the expert strong branching rule by a tailored top-k Kullback-Leibler divergence loss function. Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed branching rules. It also outperforms state-of-the-art machine-learning-based branch-and-bound methods in terms of solving speed and search tree size on all the test instances. In addition, the model can generalize to unseen instances and scale to larger instances.
- Branch-and-bound (B&B),
- combinatorial optimization,
- deep learning,
- graph neural network,
- imitation learning

FullText(HTML)

References(38)

References

[1]	P. Festa, “A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems,” in Proc. 16th Int. Conf. Transparent Optical Networks, Graz, Austria, 2014, pp. 1–20.
[2]	A. Schrijver, “On the history of combinatorial optimization (till 1960),” Handb. Oper. Res. Manage. Sci., vol. 12, pp. 1–68, 2005.
[3]	K. Abe, I. Sato, and M. Sugiyama, “Solving NP-hard problems on graphs by reinforcement learning without domain knowledge,” arXiv preprint arXiv: 1905.11623, 2020
[4]	E. Yolcu and B. Póczos, “Learning local search heuristics for Boolean satisfiability,” in Proc. 33rd Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, pp. 7992–8003.
[5]	Y. Bengio, A. Lodi, and A. Prouvost, “Machine learning for combinatorial optimization: A methodological tour d’Horizon,” Eur. J. Oper. Res., vol. 290, no. 2, pp. 405–421, Apr. 2021. doi: 10.1016/j.ejor.2020.07.063
[6]	D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, “Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning,” Discrete Optim., vol. 19, pp. 79–102, Feb. 2016. doi: 10.1016/j.disopt.2016.01.005
[7]	A. H. Land and A. G. Doig, “An automatic method for solving discrete programming problems,” in 50 Years of Integer Programming 1958–2008, M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, Eds. Berlin, Germany: Springer, 2010, pp. 105–132.
[8]	N. Vesselinova, R. Steinert, D. F. Perez-Ramirez, and M. Boman, “Learning combinatorial optimization on graphs: A survey with applications to networking,” IEEE Access, vol. 8, pp. 120388–120416, Jun. 2020. doi: 10.1109/ACCESS.2020.3004964
[9]	E. A. Silver, “An overview of heuristic solution methods,” J. Oper. Res. Soc., vol. 55, no. 9, pp. 936–956, May 2004. doi: 10.1057/palgrave.jors.2601758
[10]	C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Comput. Surv., vol. 35, no. 3, pp. 268–308, Sept. 2003. doi: 10.1145/937503.937505
[11]	H. He, H. Daume III, and J. Eisner, “Learning to search in branch and bound algorithms,” in Proc. 27th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2014, pp. 3293–3301.
[12]	E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina, “Learning to branch in mixed integer programming,” in Proc. 30th AAAI Conf. Artificial Intelligence, Phoenix, Arizona, 2016, pp. 724–731.
[13]	M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi, “Exact combinatorial optimization with graph convolutional neural networks,” in Proc. 33rd Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2019, p. 1396.
[14]	P. Gupta, M. Gasse, E. B. Khalil, M. P. Kumar, A. Lodi, and Y. Bengio, “Hybrid models for learning to branch,” in Proc. 34th Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2020, p. 1518.
[15]	G. Zarpellon, J. Jo, A. Lodi, and Y. Bengio, “Parameterizing branch-and-bound search trees to learn branching policies,” in Proc. AAAI Conf. Artificial Intelligence, 2021, pp. 3931–3939.
[16]	O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,” in Proc. 28th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2015, pp. 2692–2700.
[17]	I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio, “Neural combinatorial optimization with reinforcement learning,” in Proc. 5th Int. Conf. Learning Representations, Toulon, France, 2016.
[18]	M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč, “Deep reinforcement learning for solving the vehicle routing problem,” arXiv preprint arXiv: 1802.04240, 2018.
[19]	H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” in Proc. 31st Int. Conf. Neural Information Processing Systems, Long Beach, USA, 2017, pp. 6351–6361.
[20]	A. Mittal, A. Dhawan, S. Manchanda, S. Medya, S. Ranu, and A. Singh, “Learning heuristics over large graphs via deep reinforcement learning,” arXiv preprint arXiv: 1903.03332, 2019.
[21]	A. Nowak, S. Villar, A. S. Bandeira, and J. Bruna, “A note on learning algorithms for quadratic assignment with graph neural networks,” arXiv preprint arXiv: 1706.07450, 2017.
[22]	C. K. Joshi, T. Laurent, and X. Bresson, “An efficient graph convolutional network technique for the travelling salesman problem,” arXiv preprint arXiv: 1906.01227, 2019.
[23]	Z. Li, Q. Chen, and V. Koltun, “Combinatorial optimization with graph convolutional networks and guided tree search,” in Proc. 32nd Int. Conf. Neural Information Processing Systems, Montréal, Canada, 2018, pp. 537–546.
[24]	M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau, “Learning heuristics for the TSP by policy gradient,” in Proc. 15th Int. Conf. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Delft, The Netherlands, 2018, pp. 170–181.
[25]	W. Kool, H. Van Hoof, and M. Welling, “Attention, learn to solve routing problems,” in Proc. 7th Int. Conf. Learning Representations, New Orleans, USA, 2019.
[26]	A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in Proc. 31st Int. Conf. Neural Information Processing Systems, Long Beach, USA, 2017, pp. 5998–6008.
[27]	K. Li, T. Zhang, and R. Wang, “Deep reinforcement learning for multiobjective optimization,” IEEE Trans. Cyber., vol. 51, no. 6, pp. 3103–3114, Jun. 2021. doi: 10.1109/TCYB.2020.2977661
[28]	A. M. Alvarez, Q. Louveaux, and L. Wehenkel, “A machine learning-based approximation of strong branching,” INFORMS J. Comput., vol. 29, no. 1, pp. 185–195, Jan. 2017. doi: 10.1287/ijoc.2016.0723
[29]	C. Hansknecht, I. Joormann, and S. Stiller, “Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem,” arXiv preprint arXiv: 1805.01415, 2018.
[30]	V. Nair, S. Bartunov, F. Gimeno, I. Von Glehn, P. Lichocki, I. Lobov, B. O’Donoghue, N. Sonnerat, C. Tjandraatmadja, P. Wang, R. Addanki, T. Hapuarachchi, T. Keck, J. Keeling, P. Kohli, I. Ktena, Y. J. Li, O. Vinyals, and Y. Zwols, “Solving mixed integer programs using neural networks,” arXiv preprint arXiv: 2012.13349, 2020.
[31]	E. Mitchell, “Branch-and-cut algorithms for combinatorial optimization problems,” Handbook of Applied Optimization, vol. 1, no. 1, pp. 65–77, 2002.
[32]	A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” ACM Comput. Surv., vol. 50, no. 2, p. 21, Mar. 2018.
[33]	P. Geurts, D. Ernst, and L. Wehenkel, “Extremely randomized trees,” Mach. Learn., vol. 63, no. 1, pp. 3–42, Mar. 2006. doi: 10.1007/s10994-006-6226-1
[34]	T. Joachims, “Optimizing search engines using clickthrough data,” in Proc. 8th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Edmonton, Canada, 2002, pp. 133–142.
[35]	C. J. C. Burges, “From RankNet to LambdaRank to LambdaMART: An overview,” Microsoft Corp., Seattle, USA, Microsoft Research Technical Report MSR-TR-2010-82, 2010.
[36]	E. Balas and A. Ho, “Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study,” Combinatorial Optimization I, M. W. Padberg, Ed. Berlin, Germany: Springer, 1980, pp. 37–60.
[37]	G. Cornuejols, R. Sridharan, and J. M. Thizy, “A comparison of heuristics and relaxations for the capacitated plant location problem,” Eur. J. Oper. Res., vol. 50, no. 3, pp. 280–297, Feb. 1991. doi: 10.1016/0377-2217(91)90261-S
[38]	D. Bergman, A. A. Cire, W.-J. Van Hoeve, and J. Hooker, Decision Diagrams for Optimization. Cham, Germany: Springer, 2016.

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(5) / Tables(9)

Get Citation

PDF

XML

Article Metrics

Article views (365) PDF downloads(48)

Highlights

Traditional B&B methods, which depend on manually-designed branching heuristics, often struggle with adaptability and efficiency across diverse problem scenarios. In contrast, we propose using neural networks to automatically learn these branching heuristics
In addition the typical graph features that are commonly explored, global and historical features are designed in this work, providing a more comprehensive and richer representation of the problem state
We introduce an innovative model that combines the graph neural network with a pointer mechanism. The graph neural network processes the graph features, while the pointer mechanism assimilates the global and historical features to finally determine the variable on which to branch
Our research presents a top-k Kullback-Leibler divergence loss function, specifically designed to train the model to imitate the strong branch heuristic effectively
Notably, the proposed method consistently surpasses both expert-crafted branching rules and contemporary machine learning techniques across all tested problems. Once trained, the model demonstrates remarkable generalization abilities, effortlessly adapting to even unseen, larger instances

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

doi: 10.1109/JAS.2023.124113

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content