首页|Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

Learning to Branch in Combinatorial Optimization With Graph Pointer Networks

扫码查看
原文链接
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据
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 optimiza-tion 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 fea-tures are designated to represent the solver state.The graph neu-ral network processes graph features,while the pointer mecha-nism assimilates the global and historical features to finally deter-mine the variable on which to branch.The model is trained to imitate the expert strong branching rule by a tailored top-k Kull-back-Leibler divergence loss function.Experiments on a series of benchmark problems demonstrate that the proposed approach significantly outperforms the widely used expert-designed bran-ching rules.It also outperforms state-of-the-art machine-lear-ning-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 optimiza-tiondeep learninggraph neural networkimitation learning

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

展开 >

Xiangjiang Laboratory and the College of Systems Engineering,National University of Defense Technology,Changsha 410073,China

Institute of Automation,Chinese Academy of Sciences,Beijing 100190,China

College of Systems Engineering,National University of Defense Technology,Changsha 410073,and also with the Hunan Key Laboratory of Multi-Energy System Intelligent Interconnection Technology,Changsha 410073,China

Department of Automation,Tsinghua University,Beijing 100084,China

College of Intelligence Science and Technology,National University of Defense Technology,Changsha 410073,China

College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China

展开 >

Open Project of Xiangjiang LaboratoryScientific Project of the National University of Defense Technology(NUDT)Scientific Project of the National University of Defense Technology(NUDT)国家杰出青年科学基金国家自然科学基金

22XJ02003ZK21-0723-ZZCX-JDZ-286212209372071205

2024

10.1109/JAS.2023.124113

自动化学报(英文版)
中国自动化学会,中国科学院自动化研究所,中国科技出版传媒股份有限公司

自动化学报(英文版)

CSTPCDEI
ISSN：2329-9266
年,卷(期)：2024.11(1)
  • 38