In this dissertation, we focus on developing sampling-based algorithms for solving stochastic linear programs. The work covers both two stage and multistage versions of stochastic linear programs. In particular, we first study the two stage stochastic decomposition (SD) algorithm and present some extensions associated with SD. Specifically, we study two issues: a) are there conditions under which the regularized version of SD generates a unique solution? and b) in cases where a user is willing to sacrifice optimality, is there a way to modify the SD algorithm so that a user can trade-off solution times with solution quality? Moreover, we present our preliminary approach to address these questions. Secondly, we investigate the multistage stochastic linear programs and propose a new approach to solving multistage stochastic decision models in the presence of constraints. The motivation for proposing the multistage stochastic decomposition algorithm is to handle large scale multistage stochastic linear programs. In our setting, the deterministic equivalent problems of the multistage stochastic linear program are too large to be solved exactly. Therefore, we seek an asymptotically optimum solution by simulating the SD algorithmic process, which was originally designed for two-stage stochastic linear programs (SLPs). More importantly, when SD is implemented in a time-staged manner, the algorithm begins to take the flavor of a simulation leading to what we refer to as optimization simulation. As for multistage stochastic decomposition, there are a couple of advantages that deserve mention. One of the benefits is that it can work directly with sample paths, and this feature makes the new algorithm much easier to be integrated within a simulation. Moreover, compared with other sampling-based algorithms for multistage stochastic programming, we also overcome certain limitations, such as a stage-wise independence assumption.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/222892 |
| Date | January 2012 |
| Creators | Zhou, Zhihong |
| Contributors | Sen, Suvrajeet, Bayraksan, Guzin, Son, Young Jun, Lin, Wei Hua, Sen, Suvrajeet, Bayraksan, Guzin |
| Publisher | The University of Arizona. |
| Source Sets | University of Arizona |
| Language | English |
| Detected Language | English |
| Type | text, Electronic Dissertation |
| Rights | Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author. |
Page generated in 0.0017 seconds