Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut
复制标题
用两阶段分支割法求解两阶段随机 Steiner 树问题
DOI：
10.1007/978-3-642-17517-6_38
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Bernd Zey
中科院分区：
文献类型：
--
作者：
I. Bomze;Markus Chimani;M. Jünger;I. Ljubić;Petra Mutzel;Bernd Zey
本文研究了具有补偿和多个场景的两阶段随机模型（SSTP）下的Steiner树问题。因此，当仅知道关于终端集合的概率信息和未来边成本时，在第一阶段中购买边。在第二阶段中，实现给定场景之一，并且购买额外的边以互连（现在已知的）终端的集合。目标是选择在第一阶段购买的边集，同时最小化解决方案的总体预期成本。
We consider the Steiner tree problem under a 2-stage stochastic model with recourse and finitely many scenarios (SSTP). Thereby, edges are purchased in the first stage when only probabilistic information on the set of terminals and the future edge costs is known. In the second stage, one of the given scenarios is realized and additional edges are purchased to interconnect the set of (now known) terminals. The goal is to choose an edge set to be purchased in the first stage while minimizing the overall expected cost of the solution.