On the Applications of Stochastic Dual Dynamic Programming

Multistage stochastic programming (MSP) problems belong to a class of problems that involve a sequence of decisions made over multiple time stages under uncertainty. Many real-world problems can be effectively represented using MSPs. However, MSPs pose challenges in optimization due to their inherent difficulty and complexity. In the literature, Stochastic Dual Dynamic Programming (SDDP) has emerged as a powerful and versatile methodology for solving MSPs. This thesis showcases the applications of SDDP in handling sequential decision-making under uncertainty across various domains.

We begin with a comprehensive introduction to MSPs, exploring their practical applications and various solution approaches. Additionally, we trace the historical development of SDDP from Benders' Decomposition to its modern enhancements.

In Chapter \ref{chap:paper1}, we conduct a comprehensive survey of the diverse applications of SDDP in the literature. This includes an analysis of statistics on the prevalence of SDDP usage in various domains. Moreover, a substantial focus is placed the most common application of SDDP in the energy sector, particularly in hydro-thermal power production scheduling. The chapter outlines compelling arguments for the prominence of this specific application.

Chapter \ref{chap:paper2} introduces two valuable contributions: $\mathsf{MSPLib}$, an open-source library of problems and $\mathsf{MSPFormat}$, a standardized data format designed for benchmarking SDDP. $\mathsf{MSPLib}$ aims to facilitate the evaluation of computational performance among different SDDP implementations. It offers a wide array of instances, from real-world problems to synthetic variations with varying complexities. By incorporating $\mathsf{MSPFormat}$ into the library, a unified and consistent representation of MSPs is provided, further enhancing their usability and transferability.

In Chapter \ref{chap:paper3}, we showcase an MSP application to the optimal location of COVID-19 vaccine facilities under the threat of natural disasters. We introduce a new algorithm, named \textit{shadow price approximation} (SPA), which aims at approximating the shadow price of opening flood-prone vaccine facilities by tuning the parameters of a linear value function approximation which is present in the objective function of base optimization model. We also compare the performance of SPA against stochastic dual dynamic integer programming (SDDiP). The chapter closes with a detailed account of this model's application in two cities of a developing country.

Moving on to Chapter \ref{chap:paper4}, we introduce a novel problem class named the multistage stochastic facility location problem under facility disruption uncertainty (MSFLPD). This new class extends the classical stochastic \textit{capacitated} facility location problem to handle uncertainty arising from facility disruptions. We then present and compare two solution algorithms tailored for addressing this problem: stochastic dual dynamic integer programming (SDDiP) and shadow price approximation (SPA).