Decomposition methods for the two-stage stochastic Steiner tree problem
Decomposition methods for the two-stage stochastic Steiner tree problem
复制标题
两阶段随机斯坦纳树问题的分解方法
DOI：
10.1007/s10589-017-9966-x
复制
发表时间：
2017
影响因子：
2.2
通讯作者：
Markus Sinnl
中科院分区：
文献类型：
--
作者：
Markus Leitner;I. Ljubić;Martin Luipersbeck;Markus Sinnl
介绍了一种新的算法方法，用于解决随机Steiner树问题的基础上计算下界（对偶上升，拉格朗日松弛，Benders分解）的三个程序。我们的方法是来自一个新的整数线性规划制定，这是所有已知的配方中最强的。由此产生的方法，它依赖于从各自的双重程序检索的双重信息的相互作用，计算上限和下限，并将它们与几个规则固定变量，以减少问题实例的大小。我们的方法的有效性进行了比较，在一个广泛的计算研究与国家的最先进的精确的方法，它采用了Benders分解的基础上，两阶段的分支和切割，和遗传算法引入DIMACS实施挑战斯坦纳树。我们的研究结果表明，所提出的方法显着优于现有的，无论是从文献中的基准实例，以及在大型电信网络。
A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances. The effectiveness of our method is compared in an extensive computational study with the state-of-the-art exact approach, which employs a Benders decomposition based on two-stage branch-and-cut, and a genetic algorithm introduced during the DIMACS implementation challenge on Steiner trees. Our results indicate that the presented method significantly outperforms existing ones, both on benchmark instances from literature, as well as on large-scale telecommunication networks.
DOI：
10.1007/978-3-642-36046-6_14
发表时间：
2013
期刊：
影响因子：
--
作者：
D. Kurz;P. Mutzel;B. Zev
通讯作者：
B. Zev
随机生存网络设计问题：理论与实践
DOI：
10.1016/j.ejor.2016.06.048
发表时间：
2017
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
I. Ljubic;P. Mutzel;B. Zey
通讯作者：
B. Zey