Leitner Markus, Ljubić Ivana, Luipersbeck Martin, Sinnl Markus
1University of Vienna, Department of Statistics and Operations Research, Faculty of Business, Economics and Statistics, Vienna, Austria.
ESSEC Business School of Paris, Cergy-Pontoise, France.
Comput Optim Appl. 2018;69(3):713-752. doi: 10.1007/s10589-017-9966-x. Epub 2017 Nov 20.
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.
介绍了一种基于三种计算下界程序（对偶上升、拉格朗日松弛、本德分解）求解随机斯坦纳树问题的新算法方法。我们的方法源自一种新的整数线性规划公式，该公式在所有已知公式中被证明是最强的。由此产生的方法依赖于从各自对偶程序中检索到的对偶信息的相互作用，计算上下界，并将它们与几个固定变量的规则相结合，以减小问题实例的规模。在广泛的计算研究中，我们将该方法的有效性与基于两阶段分支切割的本德分解的最新精确方法以及在斯坦纳树的DIMACS实现挑战赛中引入的遗传算法进行了比较。我们的结果表明，所提出的方法在文献中的基准实例以及大规模电信网络上均显著优于现有方法。
