论文标题
在啤酒花约束的坦纳树问题上
On the hop-constrained Steiner tree problems
论文作者
论文摘要
霍普限制的施罐树问题（HSTP）是经典施泰纳树问题的概括。它要求提供一个最低成本子树，该子树涵盖给定图的某些指定的节点，以使树的每个节点及其根部尊重给定的hop限制。这个NP硬性问题具有许多变体，通常以整数线性程序为模型。其中两个模型是所谓的分配和基于部分订购的模型，它们（符合我们的知识）是最佳的两个最新的施泰纳树问题的最先进的配方，并带有收入，预算和HOP限制（STPRBH）。 HSTP的解决方案及其变体，例如STPRBH和霍普受限的最小跨越树问题（HMSTP）是一棵啤酒花限制的树，它是一个植根的树，其深度由给定的啤酒花限制界定。本文提供了一些理论上的结果，这些结果表明部分订购模型比该类别问题的分配模型的多面体优势。本文的计算结果以及HSTP，STPRBH和HMSTP的文献表明，部分订购模型在实践中的表现也优于分配模型。它具有更好的线性编程放松，并解决了更多实例。
The hop-constrained Steiner tree problem (HSTP) is a generalization of the classical Steiner tree problem. It asks for a minimum cost subtree that spans some specified nodes of a given graph, such that the number of edges between each node of the tree and its root respects a given hop limit. This NP-hard problem has many variants, often modeled as integer linear programs. Two of the models are so-called assignment and partial-ordering based models, which yield (up to our knowledge) the best two state-of-the-art formulations for the variant Steiner tree problem with revenues, budgets, and hop constraints (STPRBH). The solution of the HSTP and its variants such as the STPRBH and the hop-constrained minimum spanning tree problem (HMSTP) is a hop-constrained tree, a rooted tree whose depth is bounded by a given hop limit. This paper provides some theoretical results that show the polyhedral advantages of the partial-ordering model over the assignment model for this class of problems. Computational results in this paper and the literature for the HSTP, STPRBH, and HMSTP show that the partial-ordering model outperforms the assignment model in practice, too; it has better linear programming relaxation and solves more instances.
