Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse
Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse
复制标题
基于自适应分区的 SDDP 算法，用于具有固定资源的多级随机线性规划
DOI：
10.1007/s10589-021-00323-1
复制
发表时间：
2021
影响因子：
2.2
通讯作者：
Song, Yongjia
中科院分区：
文献类型：
--
作者：
Siddig, Murwan;Song, Yongjia
本文将求解具有固定补偿矩阵和固定代价向量的两阶段随机规划的自适应划分方法推广到随机过程为阶段独立的多阶段随机规划环境。所提出的算法将基于自适应划分的策略与一种流行的求解多阶段随机规划问题的方法--随机对偶动态规划(SDDP)算法相结合，主要分为两种策略。这两种策略在解决过程中细化分区的方式各不相同。特别是，我们提出了一种SDDP外的精化策略，即迭代地求解由分区产生的粗略场景树，并仅在必要时在SDDP外的单独步骤中对分区进行精化。我们还在SDDP策略中提出了一种精化策略，其中分区与SDDP算法的机制一起被精化。然后，我们在两个不同的细化方案中使用不同的树遍历策略，这些策略允许我们在一定程度上控制分区的大小。我们对一个水火发电规划问题进行了数值实验。数值结果表明，与标准SDDP算法和SDDP策略内求精算法相比，采用SDDP策略外求精的算法是有效的。
In this paper, we extend the adaptive partition-based approach for solving two-stage stochastic programs with fixed recourse matrix and fixed cost vector to the multistage stochastic programming setting where the stochastic process is assumed to be stage-wise independent. The proposed algorithms integrate the adaptive partition-based strategy with a popular approach for solving multistage stochastic programs, the stochastic dual dynamic programming (SDDP) algorithm, according to two main strategies. These two strategies are distinct from each other in the manner by which they refine the partitions during the solution process. In particular, we propose a refinement outside SDDP strategy whereby we iteratively solve a coarse scenario tree induced by the partitions, and refine the partitions in a separate step outside of SDDP, only when necessary. We also propose a refinement within SDDP strategy where the partitions are refined in conjunction with the machinery of the SDDP algorithm. We then use, within the two different refinement schemes, different tree-traversal strategies which allow us to have some control over the size of the partitions. We performed numerical experiments on a hydro-thermal power generation planning problem. Numerical results show the effectiveness of the proposed algorithms that use the refinement outside SDDP strategy in comparison to the standard SDDP algorithm and algorithms that use the refinement within SDDP strategy.
登录
查看更多内容
通过随机规划进行投资组合优化和风险管理
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
J. Dupacová
通讯作者：
J. Dupacová
影响因子：
2.7
作者：
Paul H. Zipkin
通讯作者：
Paul H. Zipkin
影响因子：
1.9
作者：
Karsten Linowsky;A. Philpott
通讯作者：
Karsten Linowsky;A. Philpott
多阶段随机规划问题分解方法中正则解的水平正则化
影响因子：
2.2
作者：
van Ackooij, Wim;de Oliveira, Welington;Song, Yongjia
通讯作者：
Song, Yongjia
使用聚类技术的水力发电系统随机水流模型
DOI：
--
发表时间：
2001
期刊：
2001 IEEE Porto Power Tech Proceedings (Cat. No.01EX502)
影响因子：
--
作者：
D.L.D.D. Jardim;M. Maceira;D. Falcão
通讯作者：
D. Falcão