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

扫码查看

原文链接

万方数据
维普

外文摘要：Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,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 problems.In 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 graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We 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 graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.

外文关键词：

degree-constrained minimum spanning tree problemminimum routing cost spanning tree problemSteiner tree problem in graphsPrim's algorithmreinforcement learning

作者：

Yuchen Shi、Congying Han、Tiande Guo

展开 >

作者单位：

School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing 100049,China

基金：

National Key R&D Program of ChinaNational Natural Science Foundation of ChinaStrategic Priority Research Program of Chinese Academy of SciencesFundamental Research Funds for the Central Universities

项目编号：

2021YFA100040311991022XDA27000000

出版年：

2024

DOI：

10.1007/s11425-022-2175-5

中国科学:数学(英文版)

中国科学院

中国科学:数学(英文版)

CSTPCD

影响因子：0.36

ISSN：1674-7283

年,卷(期)：2024.67(6)