Learning to Prune Instances of Steiner Tree Problem in Graphs
This work addresses combinatorial optimization problems for researchers and practitioners, but it is incremental as it applies an existing framework to a new problem.
The paper tackled the Steiner tree problem, a classical NP-hard combinatorial optimization problem, by applying the learning-to-prune machine learning framework, resulting in near-optimal solutions computed much faster than commercial ILP solvers, though no specific speedup numbers were provided.
We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes. This is a classical NP-hard combinatorial optimisation problem. In recent years, a machine learning framework called learning-to-prune has been successfully used for solving a diverse range of combinatorial optimisation problems. In this paper, we use this learning framework on the Steiner tree problem and show that even on this problem, the learning-to-prune framework results in computing near-optimal solutions at a fraction of the time required by commercial ILP solvers. Our results underscore the potential of the learning-to-prune framework in solving various combinatorial optimisation problems.