30 November 2012 in Mathematical Programming
29 April 2017 in Mathematical Programming
1 January 2014 in SIAM Journal on Optimization
Multistate stochastic programs pose some of the more challenging optimization problems. Because such models can become rather intractable in general, it is important to design algorithms that can provide approximations which, in the long run, yield solutions that are arbitrarily close to an optimum. In this paper, we propose such a sequential sampling method which is applicable to multistage stochastic linear programs, and we refer to it as the multistage stochastic decomposition (MSD) algorithm. This algorithm represents a dynamic extension of a regularized version of stochastic decomposition (SD). While the method allows general correlation structures, specialized streamlined versions are also possible for special cases of stagewise independent and autoregressive processes commonly incorporated in stochastic programming. As with its two-stage counterpart, the MSD algorithm is shown to provide an asymptotically optimal solution, with probability one. As a by-product of this study, we also show that SD al...
23 April 2016 in Mathematical Programming
1 December 2016 in Operations Research
Stochastic Programming (SP) has long been considered 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 paper 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 provide a stronger convergence result for SD, and introduce a new solution concept that we call the compromise decision. This new concept is attractive for algorithms that 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. We discuss three stopping criteria that enhance the reliability of the compromise decision, reducing bias and variance associated with the result. Finally our computational results cover a variety of instances from the literature, including a detailed study of SONET Switched Network (SSN), a network planning instance known to be more challenging than other test instances in the literature.
1 January 2020 in SIAM Journal on Optimization
This paper studies the class of two-stage stochastic programs with a linearly bi-parameterized recourse function defined by a convex quadratic program. A distinguishing feature of this new class of...