A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs
A parallel implementation of the nested decomposition algorithm for multistage stochastic linear programs
复制标题
多级随机线性规划嵌套分解算法的并行实现
DOI：
--
复制
发表时间：
1996
影响因子：
2.7
通讯作者：
Oleg G. Svintsitski
中科院分区：
文献类型：
--
作者：
J. Birge;Christopher J. Donohue;Derek F. Holmes;Oleg G. Svintsitski
多阶段随机线性规划可以表示各种实际决策问题。求解一个多阶段随机规划可以看作是求解一个大型的线性规划树。解决这些问题的常用方法是嵌套分解算法，它通过求解节点并在节点之间传递信息来沿着树向上移动。子树的自然独立性表明，嵌套分解算法的大部分计算工作可以在少量的快速处理器上并行运行。本文探讨了这种并行实现串行实现的优点，并比较了并行处理器的替代排序协议。一个大型测试集的实际问题的计算经验，多达150万个约束和近500万个变量表明，并行实现可能确实工作得很好，但他们需要小心处理器负载平衡。
Multistage stochastic linear programs can represent a variety of practical decision problems. Solving a multistage stochastic program can be viewed as solving a large tree of linear programs. A common approach for solving these problems is the nested decomposition algorithm, which moves up down the tree by solving nodes and passing information among nodes. The natural independence of subtrees suggests that much of the computational effort of the nested decomposition algorithm can run in parallel across small numbers of fast processors. This paper explores the advantages of such parallel implementations over serial implementations and compares alternative sequencing protocols for parallel processors. Computational experience on a large test set of practical problems with up to 1.5 million constraints and almost 5 million variables suggests that parallel implementations may indeed work well, but they require careful attention to processor load balancing.