Exact Algorithms for Plane Steiner Tree Problems: A Computational Study
Exact Algorithms for Plane Steiner Tree Problems: A Computational Study
复制标题
DOI：
10.1007/978-1-4757-3171-2_6
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
David M. Warme;P. Winter;Martin Zachariasen
中科院分区：
文献类型：
--
作者：
David M. Warme;P. Winter;Martin Zachariasen
我们提出了一个计算研究的精确算法的欧氏和直线斯坦纳树问题的平面。这些算法，这是基于完整的斯坦纳树的生成和级联，比其他方法更有效，并允许超过2000终端的问题实例的精确解决方案。完整的斯坦纳树生成算法的两个问题的变种共享许多算法思想和级联部分是相同的（整数规划制定解决的分支和切割）。给出了随机生成实例、公共库实例和具有特殊结构的”困难”实例的性能统计。此外，两个问题的变种上的比较性能的结果。
We present a computational study of exact algorithms for the Euclidean and rectilinear Steiner tree problems in the plane. These algorithms-which are based on the generation and concatenation of full Steiner trees-are much more efficient than other approaches and allow exact solutions of problem instances with more than 2000 terminals. The full Steiner tree generation algorithms for the two problem variants share many algorithmic ideas and the concatenation part is identical (integer programming formulation solved by branch-andcut). Performance statistics for randomly generated instances, public library instances and" difficult" instances with special structure are presented. Also, results on the comparative performance on the two problem variants are given.