NeuroPrim:An attention-based model for solving NP-hard spanning tree problems

作     者：Yuchen Shi Congying Han Tiande Guo 

作者机构：School of Mathematical SciencesUniversity of Chinese Academy of SciencesBeijing100049China 

出 版 物：《Science China Mathematics》 (中国科学（数学）（英文版）)

年 卷 期：2024年第67卷第6期

页      面：1359-1376页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by National Key R&D Program of China(Grant No.2021YFA1000403) National Natural Science Foundation of China(Grant No.11991022) the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000) the Fundamental Research Funds for the Central Universities 

主　　题：degree-constrained minimum spanning tree problem minimum routing cost spanning tree problem Steiner tree problem in graphs Prim's algorithm reinforcement learning 

摘      要：Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential ***,there has been growing interest in end-to-end deep neural networks for solving routing ***,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree *** this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on *** approach reduces the action and state space using Prim s algorithm and trains the resulting model using *** apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in *** results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 ***,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,*** results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.