Steiner tree: a deep reinforcement learning approach

Abstract

The Steiner tree problem is a classical combinatorial optimization problem that targets interconnecting a set of points by a network whose total length is the shortest, where the network consists of the original points and the newly added points called Steiner points. Since the problem can be reduced to the minimum spanning tree problem if the Steiner points in the optimal solution could be found, finding the optimal Steiner points is the key part of solving Steiner tree problems. Recent research shows that reinforcement learning can learn effective heuristic algorithms, suggesting a new way for computing the Steiner points. Motivated by this, we attempt to use deep learning and reinforcement learning to solve the Steiner tree problem. In our approach, we first generate a candidate set for Steiner points based on the Steiner points' property, and then compute the node representation through the attention mechanism. Based on the learned representation, we learn a policy for selecting Steiner points using the REINFORCE algorithm.