On Parallelizing Dual Decomposition in Stochastic Integer Programming
On Parallelizing Dual Decomposition in Stochastic Integer Programming
复制标题
DOI：
10.2139/ssrn.2165991
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Miles Lubin;Kipp Martin;C. Petra;B. Sandikçi
中科院分区：
文献类型：
--
作者：
Miles Lubin;Kipp Martin;C. Petra;B. Sandikçi
对于随机混合整数规划，我们从计算的角度重新审视了Caroe和Schultz的对偶分解算法，目的是使其并行化。我们解决了一个重要的瓶颈并行执行，通过确定一个配方，允许并行解决方案的主程序，通过使用结构开发的通道点求解器。我们的研究结果表明并行加速的潜力和正则化（稳定化）的重要性，在双重优化。负载不平衡被认为是并行可伸缩性的一个剩余障碍。
For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Caroe and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the master program by using structure-exploiting interior-point solvers. Our results demonstrate the potential for parallel speedup and the importance of regularization (stabilization) in the dual optimization. Load imbalance is identified as a remaining barrier to parallel scalability.