Multistage stochastic programming

Abstract

There are many practical problems where one has to make decisions sequentially based on data (observations) available at the time of the decision. Trying to make such decisions under uncertainty in some optimal way, looking forward in time, leads to the area of multistage stochastic optimization. In this thesis, we develop methodologies, algorithms, and a software package for large-scale multistage stochastic programming problems with applications in energy, airline and finance. In the first part of the thesis (chapter 2), we suggest a standardized procedure to solve multistage stochastic programs. The procedure has four steps. The first step is to model the underlying data process and build the true problem. In many applications, the underlying data process has a Markovian structure. We discuss two ways to embed the data process into the optimization problem. The second step is to discretize the true problem. Various approaches of discretization are proposed. The third step is to solve the discretized problem. A powerful tool to do that is the so-called stochastic dual dynamic programming algorithm (SDDP). Computational aspects related to this algorithm are discussed. In particular we discuss three types of stopping criteria of the algorithm. The fourth step is to evaluate the obtained policy on the true problem. This final step is of crucial importance, which is often ignored in the literature. Extensions of the methodology to risk averse and mix-integer settings are also considered. We also develop another class of algorithms based on equivalent linear programming formulations that do not rely on stochastic programming. In chapter 3, we demonstrate a new software package, MSPPy, for multistage stochastic programs based on the aforementioned methodologies. Since the popularity of the SDDP algorithm, many open-source software packages have sprung up and are able to solve a wide variety of problems. But all of them were built for the case when the underlying data process has finite number of realizations (scenarios). The newly built software package is the first one to consider problems with continuous distributions of the data processes. In the second part of the thesis (chapter 4), we propose a new variant of the SDDP algorithm, referred to as periodical SDDP. Some real-world problems often depict a seasonal behavior. In such cases, we can drastically reduce the number of stages by introducing a periodical analog of the Bellman equations, used in Markov decision process (MDP) and stochastic optimal control (SOC), and consequently applying a periodical variant of the SDDP algorithm. Since the computational complexity of the SDDP algorithm is explicitly related to the number of stages, the proposed periodical SDDP algorithm significantly reduces the computational time compared to the classical SDDP. This makes previously computationally intractable problems feasible to solve. In the last part of the thesis (chapter 5), we explore various applications in energy, airline, and finance using the MSPPy package to illustrate the methodologies and algorithms we have developed. Further, we empirically study various numerical aspects of multistage stochastic programming.