Branch-and-Price for the Steiner Tree Problem with Revenues , Budget and Hop Constraints
Branch-and-Price for the Steiner Tree Problem with Revenues , Budget and Hop Constraints
复制标题
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Markus Sinnl;Verfassung der Arbeit
中科院分区：
文献类型：
--
作者：
Markus Sinnl;Verfassung der Arbeit
本文研究了具有收入、预算和跳数约束的Steiner树问题（STPRBH），这是一个NP难的组合优化问题，并在电信网络设计中得到了应用。STPRBH的一个实例是由一个连接图定义的，该图具有一个专用的根节点，一组具有非负收入和正成本的节点分配给边缘。此外，还给出了一个跳数极限H ∈ N和一个跳数B ≥ 0.可行解的集合由所有包含根节点的Steiner树给出，其中从根节点到树中任何其他节点的每条路径最多包含H条边。此外，这种树的总边成本必须低于或等于给定的预算B。我们的目标是找到一个可行的解决方案与最大的收入，即最大化与节点的收入是解决方案的一部分。提出了基于指数多变量整数线性规划的STPRBH的几种公式。此外，基于这些配方的分支和价格的方法，允许解决的STPRBH证明最优的实例。然而，这些分支和价格方法的实际实现确实存在各种问题。因此，各种尝试，以提高其效率，如稳定技术，不同的定价策略和启发式方法来产生初始解的适用性进行了分析。此外，有前途的方法进行了相应的调整和应用到STPRBH。对已有的基准实例的测试表明，当跳数限制比较严格或正收益节点数相对较少时，所提出的分支-价格方法与现有的基于分支-切割的精确方法相比具有很强的竞争力.此外，当预算B不起作用（即足够高，不构成限制），分支和价格通常优于分支和切割。然而，应该注意的是，STPRBH的这个特定变体不是NP难的。对于具有较大跳数限制或具有大量正收入的节点的实例，所提出的分支和价格方法与分支和切割方法相比尚不具有竞争力。然而，由于实施了稳定和加速方法，这些实例也实现了分支和价格的显著加速。
This thesis deals with the Steiner tree problem with revenues, budget and hop constraints (STPRBH), an NP-hard combinatorial optimization problem with applications in telecommunications network design. An instance of the STPRBH is defined by a connected graph with a dedicated root node, a set of nodes with nonnegative revenues and positive costs assigned to edges. Furthermore, a budgetB ≥ 0 and a hop limitH ∈ N are given. The set of feasible solutions is given by all Steiner trees containing the root node, where every path from the root node to any other node in the tree contains at most H edges. Furthermore, the total edge costs of such a tree must be lower or equal to the given budget B. The goal is to find a feasible solution with maximum revenue, i.e. to maximize the sum of revenues associated with nodes which are part of the solution. Several formulations for the STPRBH based on integer linear programming using exponentially many variables are presented. Furthermore, branch-and-price approaches based on these formulations are introduced that allow for solving instances of the STPRBH to proven optimality. The practical implementations of these branch-and-price approaches do, however, suffer from various problems. Thus, the applicability of various attempts to improve their efficiency like stabilization techniques, different pricing strategies and heuristic methods to generate initial solutions is analyzed. Furthermore, promising methods are correspondingly adapted and applied to the STPRBH. Tests on previously existing benchmark instances show that the presented branch-and-price approaches are competitive with existing exact methods based on branch-and-cut when the hop limit is rather restrictive or if the number of nodes with positive revenue is relatively small. Furthermore, when the budget B does not play a role (i.e. is high enough to pose no restriction), branch-and-price usually outperforms branch-and-cut. It should be noted, however, that this specific variant of the STPRBH is not NP -hard. For instances with a large hop limit or a large number of nodes with positive revenue the proposed branch-and-price approaches are not yet competitive to branch-and-cut. Due to the implemented stabilization and acceleration methods a significant speed-up of branch-and-price has, however, been achieved for these instances too.