Parallel and distributed computing for stochastic dual dynamic programming
Parallel and distributed computing for stochastic dual dynamic programming
复制标题
DOI：
10.1007/s10287-021-00411-x
复制
发表时间：
2021-08
影响因子：
0.9
通讯作者：
Daniel Ávila;Anthony Papavasiliou;Nils Löhndorf
中科院分区：
文献类型：
--
作者：
Daniel Ávila;Anthony Papavasiliou;Nils Löhndorf
我们研究了随机对偶动态规划（SDDP）算法的不同并行化方案。我们提出了一个分类这些并行算法，这是基于并行化的概念，由场景和并行化的节点的底层随机过程。我们为每个配置开发了同步和异步版本。并行场景配置中的并行化策略旨在并行化SDDP算法前向传递中的Monte Carlo采样过程，从而并行生成大量的支持超平面。另一方面，并行节点策略旨在并行地构建动态规划值函数的单个超平面。所考虑的算法实现使用Julia和JuMP上的高性能计算集群。我们研究的有效性的方法，实现紧密的最优性差距，以及相对于越来越多的CPU的算法的可扩展性。特别是，我们研究了不同的并行化策略对性能的影响时，增加的Monte Carlo样本的数量在向前通过，并通过数值实验表明，这种增加可能是有害的。我们的研究结果表明，并行节点的战略提出了一定的好处相比，并行场景配置。
We study different parallelization schemes for the stochastic dual dynamic programming (SDDP) algorithm. We propose a taxonomy for these parallel algorithms, which is based on the concept of parallelizing by scenario and parallelizing by node of the underlying stochastic process. We develop a synchronous and asynchronous version for each configuration. The parallelization strategy in the parallelscenario configuration aims at parallelizing the Monte Carlo sampling procedure in the forward pass of the SDDP algorithm, and thus generates a large number of supporting hyperplanes in parallel. On the other hand, the parallel-node strategy aims at building a single hyperplane of the dynamic programming value function in parallel. The considered algorithms are implemented using Julia and JuMP on a high performance computing cluster. We study the effectiveness of the methods in terms of achieving tight optimality gaps, as well as the scalability properties of the algorithms with respect to an increasing number of CPUs. In particular, we study the effects of the different parallelization strategies on performance when increasing the number of Monte Carlo samples in the forward pass, and demonstrate through numerical experiments that such an increase may be harmful. Our results indicate that a parallel-node strategy presents certain benefits as compared to a parallel-scenario configuration.