Spanning trees in hypergraphs with applications to steiner trees
Spanning trees in hypergraphs with applications to steiner trees
复制标题
超图中的生成树及其在斯坦纳树中的应用
DOI：
10.18130/v3zg4b
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
David M. Warme
中科院分区：
文献类型：
--
作者：
Jeffrey S. Salowe;David M. Warme
本论文研究了几何斯坦纳树问题：给定平面上的一组终端，根据某种几何距离度量找到这些终端的最小长度互连。然而，在此过程中，它解决了一个更普遍、更广泛适用的问题，即在超图中找到最小权重生成树。已知几何斯坦纳树问题对于直线度量是 NP 完全的，对于欧几里德度量是 NP 困难的。解决这些问题的最快精确算法（实际上）使用两个阶段：首先生成一组小但足够的完整斯坦纳树（FST），然后根据该集合构建斯坦纳最小树。这些阶段分别称为 FST 生成和 FST 连接，并概述了每个阶段。 FST 连接几乎总是最昂贵的阶段，传统上是通过简单的回溯搜索或动态编程来完成的。定义了超图问题中的生成树，并证明其具有强NP完全性。然后，超图问题中的最小权重生成树（MST）的动机是通过证明 FST 串联以简单的方式简化为超图中的 MST。然后，使用子环消除约束将超图问题中的 MST 公式化为整数规划。介绍了超图多胞体中的生成树 STHGP(n)，并证明了它的许多性质。特别是，整数规划中使用的每个约束都被证明定义了 STHGP(n) 的一个方面。提出了一种基于割集约束的替代整数规划公式，但显示出其 LP 松弛比 subtour 公式的弱。给出了 STHGP(n) 中极值点数量的简单公式，从而将 Cayley 的经典树枚举问题推广到超图。提出了超图问题中MST的分支割算法。该算法应用于FST级联问题。针对大量不同规模的问题实例（最多 1000 个终端）提供了实验结果。对于每个实例都获得最佳直线树和欧几里德施泰纳树。单个 2000 个终端欧几里得实例也得到了最优解。这些结果表明，新算法是迄今为止最快的，因为先前发布的最佳 Steiner 树结果分别是直线的 70 个终端和欧几里得的 150 个终端。概述了未来工作的许多方向，最后指出，这种两阶段方法适用于任何有限维度中的任何距离度量|甚至是图表中的斯坦纳问题|假设有一个合适的 FST 生成算法可用。 xv 比 subtour 公式的算法更好。给出了 STHGP(n) 中极值点数量的简单公式，从而将 Cayley 的经典树枚举问题推广到超图。提出了超图问题中MST的分支割算法。该算法应用于FST级联问题。针对大量不同规模的问题实例（最多 1000 个终端）提供了实验结果。对于每个实例都获得最佳直线树和欧几里德施泰纳树。单个 2000 个终端欧几里得实例也得到了最优解。这些结果表明，新算法是迄今为止最快的，因为先前发布的最佳 Steiner 树结果分别是直线的 70 个终端和欧几里得的 150 个终端。概述了未来工作的许多方向，最后指出，这种两阶段方法适用于任何有限维度中的任何距离度量|甚至是图表中的斯坦纳问题|如果有合适的 FST 生成算法可用。
This dissertation examines the geometric Steiner tree problem: given a set of terminals in the plane, nd a minimum-length interconnection of those terminals according to some geometric distance metric. In the process, however, it addresses a much more general and widely applicable problem, that of nding a minimum-weight spanning tree in a hypergraph. The geometric Steiner tree problem is known to be NP-complete for the rectilinear metric, and NP-hard for the Euclidean metric. The fastest exact algorithms (in practice) for these problems use two phases: First a small but su cient set of full Steiner trees (FSTs) is generated and then a Steiner minimal tree is constructed from this set. These phases are called FST generation and FST concatenation, respectively, and an overview of each phase is presented. FST concatenation is almost always the most expensive phase, and has traditionally been accomplished via simple backtrack search or dynamic programming. The spanning tree in hypergraph problem is de ned, and is proven to be strongly NP-complete. The minimum-weight spanning tree (MST) in hypergraph problem is then motivated by showing that FST concatenation reduces to MST in hypergraph in a simple way. The MST in hypergraph problem is then formulated as an integer program using subtour elimination constraints. The spanning tree in hypergraph polytope, STHGP(n), is introduced and a number of its properties are proven. In particular, every constraint used in the integer program is shown to de ne a facet of STHGP(n). An alternate integer programming formulation based on cutset constraints is presented, but is shown to have an LP relaxation that is weaker xiv Abstract xv than that of the subtour formulation. A simple formula for the number of extreme points in STHGP(n) is shown, thereby generalizing the classical tree enumeration problem of Cayley to hypergraphs. A branch-and-cut algorithm for the MST in hypergraph problem is presented. This algorithm is applied to the FST concatenation problem. Experimental results are presented for a large set of problem instances of various sizes up to 1000 terminals. Optimal rectilinear and Euclidean Steiner trees are obtained for every instance. A single 2000 terminal Euclidean instance is also solved to optimality. These results show that the new algorithm is by far the fastest in existence, since the best previously published Steiner tree results are 70 terminals for rectilinear and 150 terminals for Euclidean, respectively. A number of directions for future work are outlined, and in conclusion it is noted that this two-phase approach works for any distance metric in any nite dimension | even the Steiner problem in graphs | provided a suitable FST generation algorithm is available.xv than that of the subtour formulation. A simple formula for the number of extreme points in STHGP(n) is shown, thereby generalizing the classical tree enumeration problem of Cayley to hypergraphs. A branch-and-cut algorithm for the MST in hypergraph problem is presented. This algorithm is applied to the FST concatenation problem. Experimental results are presented for a large set of problem instances of various sizes up to 1000 terminals. Optimal rectilinear and Euclidean Steiner trees are obtained for every instance. A single 2000 terminal Euclidean instance is also solved to optimality. These results show that the new algorithm is by far the fastest in existence, since the best previously published Steiner tree results are 70 terminals for rectilinear and 150 terminals for Euclidean, respectively. A number of directions for future work are outlined, and in conclusion it is noted that this two-phase approach works for any distance metric in any nite dimension | even the Steiner problem in graphs | provided a suitable FST generation algorithm is available.