Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse

Murwan Siddig () and Yongjia Song ()
Additional contact information
Murwan Siddig: RWTH Aachen University
Yongjia Song: Clemson University

Computational Optimization and Applications, 2022, vol. 81, issue 1, No 8, 250 pages

Abstract: Abstract 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.

Keywords: Stochastic optimization; Multistage stochastic linear programs; Partition-based approach; SDDP algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-021-00323-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:81:y:2022:i:1:d:10.1007_s10589-021-00323-1

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-021-00323-1

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().