论文标题
针对定向的施泰纳树问题的模拟退火算法
A Simulated Annealing Algorithm for the Directed Steiner Tree Problem
论文作者
论文摘要
在\ cite {siebert2019linear}作者为施泰纳树问题提供了一组整数程序（IPS），可以将其用于该问题的定向和无向设置。每个IP都找到具有特定结构的最佳坦碱树。成本最低的解决方案对应于整个问题的最佳解决方案。作者表明，每个IP的线性编程松弛是不可或缺的，而且每个IP在实例的大小中都是多项式的，因此，它们可以在多项式时间内解决。主要问题是，求解的IP数量随端子节点的数量成倍增长，这使得该方法在大型实例中不切实际。在本文中，我们建议使用\ cite {siebert2019linear}中提出的方法来解决定向的施泰纳树问题。为此，我们提出了一种动态编程算法，以有效地求解每个IP。然后，我们提供每个树结构邻域的表征。最后，我们使用所提出的算法和邻域表征使用模拟退火框架来解决问题。计算实验表明，我们方法提供的解决方案的质量要比针对施泰纳树问题的文献中提出的解决方案的质量要好。
In \cite{siebert2019linear} the authors present a set of integer programs (IPs) for the Steiner tree problem, which can be used for both, the directed and the undirected setting of the problem. Each IP finds an optimal Steiner tree with a specific structure. A solution with the lowest cost, corresponds to an optimal solution to the entire problem. The authors show that the linear programming relaxation of each IP is integral and, also, that each IP is polynomial in the size of the instance, consequently, they can be solved in polynomial time. The main issue is that the number of IPs to solve grows exponentially with the number of terminal nodes, which makes this approach impractical for large instances. In this paper, we propose a local search procedure to solve the directed Steiner tree problem using the approach presented in \cite{siebert2019linear}. In order to do this, we present a dynamic programming algorithm to solve each IP efficiently. Then we provide a characterization of the neighborhood of each tree structure. Finally, we use the proposed algorithm and the neighborhood characterization to solve the problem using a simulated annealing framework. Computational experiments show that the quality of the solutions delivered by our approach is better than the ones presented in the literature for the directed Steiner tree problem.
