Title: Large Scale Multistage Stochastic Integer Programming with Applications in Electric Power Systems

Advisors: Dr. Shabbir Ahmed, Dr. Andy Sun

Committee members:
Dr. Alexander Shapiro
Dr. Natashia Boland
Dr. Andy Philpott (University of Auckland)

Date and Time: April 28th (Friday), 2017, at 1:00 PM

Location: Groseclose 402 (Advisory Boardroom)

Summary:
Multistage stochastic integer programming (MSIP) is a framework for sequential decision making under uncertainty, where the uncertainty is modeled by a general stochastic process, and the decision space involves integer variables and complicated constraints. Many power system applications, such as generation capacity planning and scheduling under uncertainty stemming from renewable generation, demand variability and price volatility, can be naturally formulated as MSIP problems. In this thesis, we develop general purpose solution methods for large-scale MSIP problems and demonstrate their effectiveness on various power systems applications.

In the first part of this thesis, we consider an MSIP approach for electrical power generation capacity expansion problems under demand and fuel price uncertainty. We propose a partially adaptive stochastic mixed integer optimization model in which the capacity expansion plan is fully adaptive to the uncertainty evolution up to a certain period, and is static thereafter. Any solution to the partially adaptive model is feasible to the multistage model and we provide analytical bounds on the quality of such a solution. We propose an algorithm that solves a sequence of partially adaptive models, to recursively construct an approximate solution to the multistage problem. We apply the proposed approach to a realistic generation expansion case study.

In the second part of this thesis, we develop decomposition algorithms for general MSIP problems with binary state variables. By exploiting the binary nature of the state variables, we extend the nested Benders decomposition algorithm to this problem class. Key to our developments are new families of cuts that guarantee finite convergence of the proposed algorithm. We also propose a stochastic variant of the nested Benders decomposition algorithm, called Stochastic Dual Dynamic integer Programming (SDDiP), and give a rigorous proof of its finite convergence with probability one to an optimal policy. We provide extensive computational results using the SDDiP approach for generation capacity planning, portfolio optimization, and airline revenue management problems.

The final part of this thesis focuses on adapting the SDDiP approach to solve the multistage stochastic unit commitment (MSUC) problem. Unit commitment is a key operational problem in power systems used to determine the optimal generation schedule over the next day or week. Incorporating uncertainty in this already difficult optimization problem imparts severe challenges. We reformulate the MSUC problem such that each stage problem only depends on information from the previous stage and the uncertainty realization. This new formulation is amenable to our SDDiP approach. We propose a variety of computational enhancements to adapt the method to MSUC. Through extensive computational results, we demonstrate the effectiveness of our approach in solving realistic scale MSUC problems.