Skip to main content
Springer Nature Link
Log in

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

  • Articles
  • AI Methods for Optimization Problems
  • Published:
Science China Mathematics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Agarwal Y K, Venkateshan P. New valid inequalities for the optimal communication spanning tree problem. INFORMS J Comput, 2019, 31: 268–284

    Article  MathSciNet  Google Scholar 

  2. Ahmed R, Turja M A, Sahneh F D, et al. Computing Steiner trees using graph neural networks. arXiv:2108.08368, 2021

  3. Andrade R, Lucena A, Maculan N. Using Lagrangian dual information to generate degree constrained spanning trees. Discrete Appl Math, 2006, 154: 703–717

    Article  MathSciNet  Google Scholar 

  4. Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM, 1998, 45: 753–782

    Article  MathSciNet  Google Scholar 

  5. Bastos M P, Ribeiro C C. Reactive tabu search with path-relinking for the Steiner problem in graphs. In: Essays and Surveys in Metaheuristics, vol. 15. Boston: Springer, 2002, 15: 39–58

    Google Scholar 

  6. Bello I, Pham H, Le Q V, et al. Neural combinatorial optimization with reinforcement learning. arXiv:1611.09940, 2017

  7. Bicalho L H, da Cunha A S, Lucena A. Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem. Comput Optim Appl, 2016, 63: 755–792

    Article  MathSciNet  Google Scholar 

  8. Boldon B, Deo N, Kumar N. Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine. Parallel Comput, 1996, 22: 369–382

    Article  Google Scholar 

  9. Bonnet E, Sikora F. The PACE 2018 parameterized algorithms and computational experiments challenge: The third iteration. In: Proceedings of the International Petroleum Environmental Conference. Leibniz International Proceedings in Informatics, vol. 115. Wadern: Schloss Dagstuhl Leibniz-Zent Inform, 2018, 1–15

    Google Scholar 

  10. Borůvka O. O jisíém problému minimálním. Praca Moravske Prirodovedecke Spolecnosti, 1926, 3: 37–58

    Google Scholar 

  11. Bouchachia A, Prossegger M. A hybrid ensemble approach for the Steiner tree problem in large graphs: A geographical application. Appl Soft Comput, 2011, 11: 5745–5754

    Article  Google Scholar 

  12. Bresson X, Laurent T. The Transformer network for the traveling salesman problem. arXiv:2103.03012, 2021

  13. Bui T N, Deng X H, Zrncic C M. An improved ant-based algorithm for the degree-constrained minimum spanning tree problem. IEEE Trans Evol Comput, 2012, 16: 266–278

    Article  Google Scholar 

  14. Bui T N, Zrncic C M. An ant-based algorithm for finding degree-constrained minimum spanning tree. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM Press, 2006, 11–18

    Chapter  Google Scholar 

  15. Byrka J, Grandoni F, Rothvoß T, et al. An improved LP-based approximation for Steiner tree. In: Proceedings of the 42nd ACM Symposium on Theory of Computing. New York: ACM, 2010, 583–592

    Google Scholar 

  16. Caccetta L, Hill S P. A branch and cut method for the degree-constrained minimum spanning tree problem. Networks, 2001, 37: 74–83

    Article  MathSciNet  Google Scholar 

  17. Campos R, Ricardo M. A fast algorithm for computing minimum routing cost spanning trees. Comput Networks, 2008, 52: 3229–3247

    Article  Google Scholar 

  18. Chlebík M, Chlebíková J. The Steiner tree problem on graphs: Inapproximability results. Theoret Comput Sci, 2008, 406: 207–214

    Article  MathSciNet  Google Scholar 

  19. Choque J N C. Optimal communication spanning tree. Master’s Thesis. São Paulo: Universidade de São Paulo, 2021

    Book  Google Scholar 

  20. da Cunha A S, Lucena A. Lower and upper bounds for the degree-constrained minimum spanning tree problem. Networks, 2007, 50: 55–66

    Article  MathSciNet  Google Scholar 

  21. Dai H J, Khalil E B, Zhang Y Y, et al. Learning combinatorial optimization algorithms over graphs. arXiv:1704.01665, 2018

  22. de Aragão M P, Uchoa E, Werneck R F. Dual heuristics on the exact solution of large Steiner problems. Electron Notes Discrete Math, 2001, 7: 150–153

    Article  MathSciNet  Google Scholar 

  23. Delbem A C B, de Carvalho A, Policastro C A, et al. Node-depth encoding for evolutionary algorithms applied to network design. In: Genetic and Evolutionary Computation, vol. 3102. Berlin-Heidelberg: Springer, 2004, 678–687

    Google Scholar 

  24. Ding M, Han C Y, Guo T D. High generalization performance structured self-attention model for knapsack problem. Discrete Math Algorithms Appl, 2021, 13: 2150076

    Article  MathSciNet  Google Scholar 

  25. Doan M N. An effective ant-based algorithm for the degree-constrained minimum spanning tree problem. In: 2007 IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007, 485–491

    Chapter  Google Scholar 

  26. Drori I, Kharkar A, Sickinger W R, et al. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv:2006.03750, 2020

  27. Du H Z, Yan Z, Xiang Q, et al. Vulcan: Solving the Steiner tree problem with graph neural networks and deep reinforcement learning. arXiv:2111.10810, 2021

  28. Duin C, Voß S. Efficient path and vertex exchange in Steiner tree algorithms. Networks, 1997, 29: 89–105

    Article  MathSciNet  Google Scholar 

  29. Esbensen H. Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm. Networks, 1995, 26: 173–185

    Article  Google Scholar 

  30. Fages J G, Lorca X, Rousseau L M. The salesman and the tree: The importance of search in CP. Constraints, 2016, 21: 145–162

    Article  MathSciNet  Google Scholar 

  31. Fischetti M, Lancia G, Serafini P. Exact algorithms for minimum routing cost trees. Networks, 2002, 39: 161–173

    Article  MathSciNet  Google Scholar 

  32. Furer M, Raghavachari B. Approximating the minimum-degree Steiner tree to within one of optimal. J Algorithms, 1994, 17: 409��423

    Article  MathSciNet  Google Scholar 

  33. Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-completeness, 27th ed. New York: Freeman, 1979

    Google Scholar 

  34. Goemans M. Minimum bounded degree spanning trees. In: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science. Berkeley: IEEE, 2006, 273–282

    Google Scholar 

  35. Guo T D, Han C Y, Tang S Q. Machine Learning Methods for Combinatorial Optimization (in Chinese). Beijing: Kexue Chubanshe (Science Press), 2019

    Google Scholar 

  36. Guo T D, Han C Y, Tang S Q, et al. Solving combinatorial problems with machine learning methods. In: Nonlinear Combinatorial Optimization, vol. 147. Cham: Springer, 2019, 207–229

    Chapter  Google Scholar 

  37. Hubbs C D, Perez H D, Sarwar O, et al. OR-Gym: A reinforcement learning library for operations research problems. arXiv:2008.06319, 2020

  38. Huy N V, Nghia N D. Solving graphical Steiner tree problem using parallel genetic algorithm. In: 2008 IEEE International Conference on Research, Innovation and Vision for the Future in Computing and Communication Technologies. Ho Chi Minh City: IEEE, 2008, 29–35

    Chapter  Google Scholar 

  39. Johnson D S, Lenstra J K, Kan A H G R. The complexity of the network design problem. Networks, 1978, 8: 279–285

    Article  MathSciNet  Google Scholar 

  40. Julstrom B A. The blob code is competitive with edge-sets in genetic algorithms for the minimum routing cost spanning tree problem. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation. New York: ACM, 2005: 585–590

    Google Scholar 

  41. Kapsalis A, Rayward-Smith V J, Smith G D. Solving the graphical Steiner tree problem using genetic algorithms. J Oper Res Soc, 1993, 44: 397–406

    Article  Google Scholar 

  42. Karp R M. Reducibility among combinatorial problems. In: Complexity of Computer Computations. New York: Plenum, 1972, 85–103

    Chapter  Google Scholar 

  43. Khakhulin T, Schutski R, Oseledets I. Learning Elimination Ordering for Tree Decomposition Problem. Cambridge: MIT Press, 2020

    Google Scholar 

  44. Kingma D P, Ba J. Adam: A method for stochastic optimization. arXiv:1412.6980, 2017

  45. Koch T, Martin A. Solving Steiner tree problems in graphs to optimality. Networks, 1998, 32: 207–232

    Article  MathSciNet  Google Scholar 

  46. Kool W, Van Hoof H, Welling M. Attention, learn to solve routing problems! arXiv:1803.08475, 2019

  47. Kruskal J B. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Amer Math Soc, 1956, 7: 48–50

    Article  MathSciNet  Google Scholar 

  48. Kwon Y D, Choo J, Kim B, et al. POMO: Policy optimization with multiple optima for reinforcement learning. Adv Neural Inform Proc Syst, 2020, 33: 21188–21198

    Google Scholar 

  49. Leitner M, Ljubić I, Luipersbeck M, et al. A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems. INFORMS J Comput, 2018, 30: 402–420

    Article  MathSciNet  Google Scholar 

  50. Lucena A, Beasley J E. A branch and cut algorithm for the Steiner problem in graphs. Networks, 1998, 31: 39–59

    Article  MathSciNet  Google Scholar 

  51. Masone A, Nenni M E, Sforza A, et al. The minimum routing cost tree problem: State of the art and a core-node based heuristic algorithm. Soft Comput, 2019, 23: 2947–2957

    Article  Google Scholar 

  52. Narula S C, Ho C A. Degree-constrained minimum spanning tree. Comput Oper Res, 1980, 7: 239–249

    Article  Google Scholar 

  53. Nazari M, Oroojlooy A, Snyder L V, et al. Reinforcement learning for solving the vehicle routing problem. In: Advances in Neural Information Processing Systems, vol. 31. La Jolla: NIPS, 2018, 1–11

    Google Scholar 

  54. Polzin T, Daneshmand S V. Improved algorithms for the Steiner problem in networks. Discrete Appl Math, 2001, 112: 263–300

    Article  MathSciNet  Google Scholar 

  55. Presti G L, Re G L, Storniolo P, et al. A grid enabled parallel hybrid genetic algorithm for SPN. In: Computational Science, vol. 3036. Berlin-Heidelberg: Springer, 2004, 156–163

    Google Scholar 

  56. Prim R C. Shortest connection networks and some generalizations. Bell Syst Tech J, 1957, 36: 1389–1401

    Article  Google Scholar 

  57. Qu R, Xu Y, Castro J P, et al. Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems. J Heuristics, 2013, 19: 317–342

    Article  Google Scholar 

  58. Raidl G R, Julstrom B A. Edge sets: An effective evolutionary coding of spanning trees. IEEE Trans Evol Comput, 2003, 7: 225–239

    Article  Google Scholar 

  59. Ribeiro C C, De Souza M C. Tabu search for the Steiner problem in graphs. Networks, 2000, 36: 138–146

    Article  MathSciNet  Google Scholar 

  60. Ribeiro C C, Uchoa E, Werneck R F. A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J Comput, 2002, 14: 228–246

    Article  MathSciNet  Google Scholar 

  61. Sattari S, Didehvar F. Variable neighborhood search approach for the minimum routing cost spanning tree problem. Int J Oper Res, 2013, 10: 153–160

    MathSciNet  Google Scholar 

  62. Sattari S, Didehvar F. A metaheuristic algorithm for the minimum routing cost spanning tree problem. Iranian J Oper Res, 2015, 6: 65–78

    Google Scholar 

  63. Scott A J. The optimal network problem: Some computational procedures. Transp Res, 1969, 3: 201–210

    Article  Google Scholar 

  64. Singh A. A new heuristic for the minimum routing cost spanning tree problem. In: Proceedings of the 11th International Conference on Information Technology. Los Alamitos: IEEE, 2008, 9–13

    Google Scholar 

  65. Singh A, Sundar S. An artificial bee colony algorithm for the minimum routing cost spanning tree problem. Soft Comput, 2011, 15: 2489–2499

    Article  Google Scholar 

  66. Singh K, Sundar S. A hybrid genetic algorithm for the degree-constrained minimum spanning tree problem. Soft Comput, 2020, 24: 2169–2186

    Article  Google Scholar 

  67. Singh M, Lau L C. Approximating minimum bounded degree spanning trees to within one of optimal. J ACM, 2015, 62: 1–19

    Article  MathSciNet  Google Scholar 

  68. Sutton R S, McAllester D, Singh S, et al. Policy gradient methods for reinforcement learning with function approximation. Adv Neural Inform Proc Syst, 1999, 12: 1057–1063

    Google Scholar 

  69. Takahashi H, Matsuyama A. An approximate solution for the Steiner problem in graphs. Math Jpn, 1980, 24: 573–577

    MathSciNet  Google Scholar 

  70. Tan Q P. A heuristic approach for solving minimum routing cost spanning tree problem. Int J Mach Learn Comput, 2012, 2: 406–409

    Article  Google Scholar 

  71. Tan Q P. A genetic approach for solving minimum routing cost spanning tree problem. Int J Mach Learn Comput, 2012, 2: 410–414

    Article  Google Scholar 

  72. Tilk C, Irnich S. Combined column-and-row-generation for the optimal communication spanning tree problem. Comput Oper Res, 2018, 93: 113–122

    Article  MathSciNet  Google Scholar 

  73. Uchoa E, Werneck R F. Fast local search for the Steiner problem in graphs. ACM J Exp Algorithmics, 2012, 17: Article No. 2.2

  74. Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need. Adv Neural Inform Proc Syst, 2017, 30: 6000–6010

    Google Scholar 

  75. Vinyals O, Fortunato M, Jaitly N. Pointer networks. Adv Neural Inform Proc Syst, 2015, 28: 2692–2700

    Google Scholar 

  76. Wang C G, Han C Y, Guo T D, et al. Solving uncapacitated P-median problem with reinforcement learning assisted by graph attention networks. Appl Intell, 2023, 53: 2010–2025

    Article  Google Scholar 

  77. Wang C G, Yang Y D, Slumbers O, et al. A game-theoretic approach for improving generalization ability of TSP solvers. arXiv:2110.15105, 2022

  78. Wang Q, Hao Y S, Cao J. Learning to traverse over graphs with a Monte Carlo tree search-based self-play framework. Engrg Appl Artificial Intell, 2021, 105: 104422

    Article  Google Scholar 

  79. Wong R T. Worst-case analysis of network design problem heuristics. SIAM J Algebr Discrete Methods, 1980, 1: 51–63

    Article  MathSciNet  Google Scholar 

  80. Wu B Y, Lancia G, Bafna V, et al. A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J Comput, 2000, 29: 761–778

    Article  MathSciNet  Google Scholar 

  81. Zetina C A, Contreras I, Fernandez E, et al. Solving the optimum communication spanning tree problem. European J Oper Res, 2019, 273: 108–117

    Article  MathSciNet  Google Scholar 

  82. Zheng W J, Wang D L, Song F G. OpenGraphGym: A parallel reinforcement learning framework for graph optimization problems. In: Computational Science, vol. 12141. Cham: Springer, 2020, 439–452

    Google Scholar 

Download references

Acknowledgements

This work was 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) and the Fundamental Research Funds for the Central Universities.

Author information

Authors and Affiliations

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

    Yuchen Shi, Congying Han & Tiande Guo

Authors
  1. Yuchen Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Congying Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tiande Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tiande Guo.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shi, Y., Han, C. & Guo, T. NeuroPrim: An attention-based model for solving NP-hard spanning tree problems. Sci. China Math. 67, 1359–1376 (2024). https://doi.org/10.1007/s11425-022-2175-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11425-022-2175-5

Keywords

MSC(2020)

Search

Navigation