Steiner tree: a deep reinforcement learning approach
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
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.
Description
Keywords
Deep learning, Reinforcement learning, Steiner tree, Combinatorial optimization, Networks