An exact algorithm for the node weighted Steiner tree problem
An exact algorithm for the node weighted Steiner tree problem
复制标题
节点加权斯坦纳树问题的精确算法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
M. Trubian
中科院分区：
文献类型：
--
作者：
R. Cordone;M. Trubian
摘要。节点加权施罐树问题（NW-STP）是施纳树问题的概括。 Engevalls：strlbn：98中提出的拉格朗日启发式方法，根据Lucena：92中的工作，通过放松普遍的子程度消除限制的指数式家族来解决该问题，并仅考虑到违法的计算收益。在Engevalls：strlbn：98计算结果是指最多一百个顶点的完整图。在本文中，我们基于此公式提出了一种分支结合的算法。它在文献的实例上的表现证实了该方法的有效性。对新生成的基准问题集（与现实世界应用更相似）的实验表明，该方法仍然有效，前提是引入了边界过程和预处理阶段的适当改进。该算法求解了最优性，所有考虑的实例最多可达一千个顶点，除了11个硬实例，源自类似问题的文献，奖品收集了Steiner树问题。
Abstract.The Node Weighted Steiner Tree Problem(NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances, derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem.