Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction

Suvrajeet Sen () and Yifan Liu ()
Additional contact information
Suvrajeet Sen: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089
Yifan Liu: Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California 90089

Operations Research, 2016, vol. 64, issue 6, 1422-1437

Abstract: 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.

Keywords: stochastic linear programming; stochastic decomposition; computational experiments (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1526 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:6:p:1422-1437

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().