Journal
OPERATIONS RESEARCH
Volume 64, Issue 6, Pages 1422-1437Publisher
INFORMS
DOI: 10.1287/opre.2016.1526
Keywords
stochastic linear programming; stochastic decomposition; computational experiments
Funding
- National Science Foundation [CMMI 0900070]
- AFOSR [FA9550-13-1-0015, FA9550-15-1-0267]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available