Computational stochastic programming with stochastic decomposition

Stochastic Programming (SP) has long been considered as a well-justified yet computationally challenging paradigm for practical applications. Computational studies in the literature often involve approximating a large number of scenarios by using a small number of scenarios to be processed via deterministic solvers, or running Sample Average Approximation on some genre of high performance machines so that statistically acceptable bounds can be obtained. In this dissertation we show that for a class of stochastic linear programming problems, an alternative approach known as Stochastic Decomposition (SD) can provide solutions of similar quality, in far less computational time using ordinary desktop or laptop machines of today. In addition to these compelling computational results, we also provide a stronger convergence result for SD, and introduce a new solution concept which we refer to as the compromise decision. This new concept is attractive for algorithms which call for multiple replications in sampling-based convex optimization algorithms. For such replicated optimization, we show that the difference between an average solution and a compromise decision provides a natural stopping rule. ❧ SD is a sequential sampling scheme combined with Benders’ like decomposition method for solving two stage stochastic linear programs with recourse. It exploits the special structures of the recourse problem to generate function approximations in an efficient manner. However, randomness is only allowed in the second stage right hand side and technology matrix associated with the first stage decision variables. In the second part of this dissertation, we relax this assumption to accommodate randomness of the second stage cost coefficients. Finally our computational results cover a variety of instances from the literature, and we further scale some operations management applications up to a level that is previously considered out of bounds for stochastic programming.