Adaptive Benders decomposition and enhanced SDDP for multistage stochastic programs with block-separable multistage recourse
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912508382543872 |
|---|---|
| author | Mazzi, Nicolò Mckinnon, Ken Zhang, Hongyu |
| author_facet | Mazzi, Nicolò Mckinnon, Ken Zhang, Hongyu |
| contents | This paper proposes an algorithm to efficiently solve multistage stochastic programs with block separable recourse where each recourse problem is a multistage stochastic program with stage-wise independent uncertainty. The algorithm first decomposes the full problem into a reduced master problem and subproblems using Adaptive Benders decomposition. The subproblems are then solved by an enhanced SDDP. The enhancement includes (1) valid bounds at each iteration, (2) a path exploration rule, (3) cut sharing among subproblems, and (4) guaranteed δ-optimal convergence. The cuts for the subproblems are then shared by calling adaptive oracles. The key contribution of the paper is the first algorithm for solving this class of problems. The algorithm is demonstrated on a power system investment planning problem with multi-timescale uncertainty. The case study results show that (1) the proposed algorithm can efficiently solve this type of problem, (2) deterministic wind modelling underestimate the objective function, and (3) stochastic modelling of wind leads to different investment decisions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_21624 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adaptive Benders decomposition and enhanced SDDP for multistage stochastic programs with block-separable multistage recourse Mazzi, Nicolò Mckinnon, Ken Zhang, Hongyu Optimization and Control Systems and Control This paper proposes an algorithm to efficiently solve multistage stochastic programs with block separable recourse where each recourse problem is a multistage stochastic program with stage-wise independent uncertainty. The algorithm first decomposes the full problem into a reduced master problem and subproblems using Adaptive Benders decomposition. The subproblems are then solved by an enhanced SDDP. The enhancement includes (1) valid bounds at each iteration, (2) a path exploration rule, (3) cut sharing among subproblems, and (4) guaranteed δ-optimal convergence. The cuts for the subproblems are then shared by calling adaptive oracles. The key contribution of the paper is the first algorithm for solving this class of problems. The algorithm is demonstrated on a power system investment planning problem with multi-timescale uncertainty. The case study results show that (1) the proposed algorithm can efficiently solve this type of problem, (2) deterministic wind modelling underestimate the objective function, and (3) stochastic modelling of wind leads to different investment decisions. |
| title | Adaptive Benders decomposition and enhanced SDDP for multistage stochastic programs with block-separable multistage recourse |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2507.21624 |