Stochastic survivable network design problems: Theory and practice
Stochastic survivable network design problems: Theory and practice
复制标题
随机生存网络设计问题：理论与实践
DOI：
10.1016/j.ejor.2016.06.048
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
B. Zey
中科院分区：
文献类型：
--
作者：
I. Ljubic;P. Mutzel;B. Zey
在一个有资源和有限个场景的两阶段随机模型下，研究了具有边连通要求的可生存网络设计问题。对于自然空间中的边缘变量的表述，我们证明了定义底层多面体的小平面的不等式可以从确定性的对应关系中得到。此外，利用图的定向性质，我们引入了更强的基于割的公式。对于所提出的混合整数规划模型，我们提出了一种基于分解模型的两阶段分枝割算法。为了提高计算速度，本文提出了一种新的L分解最优割的加强方法，该方法计算速度快，易于实现。一项计算研究显示了分解和切割强化的好处--这显著减少了主迭代次数和计算运行时间。此外，我们还对场景生成方法的稳定性进行了评估，并分析了随机解的价值。
We study survivable network design problems with edge-connectivity requirements under a two-stage stochastic model with recourse and finitely many scenarios. For the formulation in the natural space of edge variables we show that facet defining inequalities of the underlying polytope can be derived from the deterministic counterparts. Moreover, by using graph orientation properties we introduce stronger cut-based formulations. For solving the proposed mixed integer programing models, we suggest a two-stage branch&cut algorithm based on a decomposed model. In order to accelerate the computations, we suggest a new technique for strengthening the decomposed L-shaped optimality cuts which is computationally fast and easy to implement. A computational study shows the benefit of the decomposition and the cut strengthening – which significantly reduces the number of master iterations and the computational running time. Moreover, we evaluate the stability of the scenario generation method and analyze the value of the stochastic solution.
登录
查看更多内容
具有有界环的两条边连通子图：多面体结果和分支割法
影响因子：
2.7
作者：
B. Fortz;A. Mahjoub;S. McCormick;Pierre Pesneau
通讯作者：
Pierre Pesneau
影响因子：
4.8
作者：
H. Sherali;B. Lunday
通讯作者：
H. Sherali;B. Lunday
用两阶段分支割法求解两阶段随机 Steiner 树问题
DOI：
10.1007/978-3-642-17517-6_38
发表时间：
2010
期刊：
SIAM J. Comput.
影响因子：
--
作者：
I. Bomze;Markus Chimani;M. Jünger;I. Ljubić;Petra Mutzel;Bernd Zey
通讯作者：
Bernd Zey
第十二届 Aussois 组合优化研讨会的踪迹
影响因子：
2.7
作者：
M. Jünger;T. Liebling;D. Naddef;W. Pulleyblank;G. Reinelt;G. Rinaldi;L. Wolsey
通讯作者：
L. Wolsey
影响因子：
2.1
作者：
Markus Leitner;Mario Ruthmair;G. Raidl
通讯作者：
G. Raidl