Solving the Node-Weighted Steiner Tree Problem using Reinforcement Learning

The node-weighted Steiner tree problem is a significant issue in network design, with broad applications including telecommunications network construction, offshore oilfield development planning, and wireless ad-hoc networks. The objective of the node-weighted Steiner tree problem is to find a subtree within a given undirected graph that has the minimum total weight and includes all specified terminals. This problem is NP-hard, typically requiring complex algorithm design and exponential time. We have combined graph neural networks and deep reinforcement learning techniques to propose a new solution method. By encoding the structural information of the graph into vector form through graph neural networks and self-attention networks, and optimizing decisions using a reinforcement learning strategy network, we efficiently construct the desired node-weighted Steiner tree. To validate the model's effectiveness, we conducted extensive experiments on various types and sizes of generated graphs, covering different numbers of endpoints. The results show that in scale-free networks (BA), our algorithm performs equivalently to SCIP, with both achieving a Gap value of 0. In small-world networks (WS) and complete graphs (K), our algorithm closely matches SCIP's performance, with the highest Gap values being 0.3% and 1.76%, respectively, indicating that our algorithm can closely approximate SCIP's performance in handling these network structures., In random graphs (ER) and random regular graphs (RR), while there is a performance discrepancy between our algorithm and SCIP, the maximum gap does not exceed 5.76%. These findings demonstrate that our algorithm performs well in solving the node-weighted Steiner tree problem.