Multi-stage Stochastic Capacity Expansion: Models and Algorithms

Abstract

In this dissertation, we study several stochastic capacity expansion models in the presence of permanent, spot market, and contract capacity for acquisition. Using a scenario tree approach to handle the data uncertainty of the problems, we develop multi-stage stochastic integer programming formulations for these models. First, we study multi-period single resource stochastic capacity expansion problems, where different sources of capacity are available to the decision maker. We develop efficient algorithms that can solve these models to optimality in polynomial time. Second, we study multi-period stochastic network capacity expansion problems with different sources for capacity. The proposed models are NP-hard multi-stage stochastic integer programs and we develop an efficient, asymptotically convergent approximation algorithm to solve them. Third, we consider some decomposition algorithms to solve the proposed multi-stage stochastic network capacity expansion problem. We propose an enhanced Benders' decomposition algorithm to solve the problem, and a Benders' decomposition-based heuristic algorithm to find tight bounds for it. Finally, we extend the stochastic network capacity expansion model by imposing budget restriction on permanent capacity acquisition cost. We design a Lagrangian relaxation algorithm to solve the model, including heuristic methods to find tight upper bounds for it.