论文标题
学会修剪图表中的坦纳树问题
Learning to Prune Instances of Steiner Tree Problem in Graphs
论文作者
论文摘要
我们考虑了给出一组节点的图表上的施泰纳树问题，目的是找到一个最小重量的树子图，其中包含给定集合中的所有节点，可能包括其他节点。这是一个经典的NP-HARD组合优化问题。近年来，一个称为“学习至上的”的机器学习框架已成功地用于解决各种组合优化问题。在本文中，我们在Steiner树问题上使用了此学习框架，并表明即使在这个问题上，学习到本文的框架也会在商业ILP求解器所需的一小部分时间内计算近乎最佳的解决方案。我们的结果强调了学习对培训框架解决各种组合优化问题的潜力。
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.
