Doctoral Dissertations
Date of Award
5-1999
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Major
Management Science
Major Professor
N. C. P. Edirisinghe
Committee Members
Carl Wagner, Charles Noon, Ham Bozdogan
Abstract
Multistage stochastic programming is a tool for modeling dynamic sequential decision making problems which involve making a sequence of decisions under uncertainty of some future events. Such models have been successfully used for many applications including planning problems in finance, economics, production, engineering, and agriculture. We focus on models in which uncertainty is described by a set of discrete scenarios associated with known probabilities. The computational difficulty of such models is mainly due to the large number of future scenarios that need to be analyzed in the process of determining implementable decisions sequentially over time.
In Edirisinghe (1996) and Edirisinghe and You (1996), a scenario approximation method was proposed and its use in solving two-stage stochastic programs effectively was demonstrated. The two-stage scenario approximation method utilizes the second-order moment information and simplicial domains of the scenario space to determine representative scenario clusters. The resulting problems are much smaller in size and provide lower and upper approximations. By successively partitioning the scenario space, the approximations can be iteratively refined to a desired accuracy. We extend this method to solve multistage stochastic programs.
In the multistage case, we apply the scenario approximation procedure to the scenario space spanning the entire decision horizon. In this way, the number of approximating scenarios is small. However, the solutions converge to that for the two-stage equivalent of the multistage problem, which is the true multistage problem without nonanticipativity constraints. By restricting the technology matrices (or the tender information) to be nonstochastic in the multistage models, we derive appropriate nonanticipativity constraints from the relationships between the true multistage model and the approximating ones. Iterative approximation coupled with the derived nonanticipativity constraints provide a valid methodology for solving multistage stochastic programming model. Decomposition algorithms are designed to solve the problem more efficiently.
Recommended Citation
You, Guey-Mei, "New solution methodologies for multi-period stochastic programming decision models. " PhD diss., University of Tennessee, 1999.
https://trace.tennessee.edu/utk_graddiss/8958