What is it about?
Sampling-based algorithms produce sampled value functions. By averaging these sampled value functions, and then optimizing the grand average, one obtains a reduced variance compromise solution.
Featured Image
Why is it important?
Sampling-based (Monte-Carlo) algorithms are prone to variance, making decisions to be error-prone. The common approach is to estimate the confidence interval of given solution to some degree of accuracy, and to then choose the most promising one. This process is computationally intensive because Monte-Carlo estimates are slow to converge, and replicating such optimization is even more time consuming. For certain classes of problems, such as two-stage stochastic linear programs with fixed and complete recourse, sampled value functions can be created efficiently, and optimizing the grand-mean value function can be performed efficiently for two-stage stochastic linear programs. This not only reduces variance, but is faster than choosing the best among many sampled decisions. This paper provides both theoretical and computational evidence.
Perspectives
Stochastic Linear Programming (SLP) has been touted for many years as "the real problem of Linear Programming". For a variety of reasons however, this class of models has been difficult to support in industrial applications. Sampling-based Stochastic Decomposition algorithm provide a data-driven approach which reduces the need for careful (manual) "carpentry" that is often used to create scenarios for SLP. However, sampling introduces error into the decision process. This paper helps reduce variance by using compromise decisions as explained in the section on "Why is it important?"
Dr. Suvrajeet Sen
University of Southern California
Read the Original
This page is a summary of: Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction, Operations Research, December 2016, INFORMS,
DOI: 10.1287/opre.2016.1526.
You can read the full text:
Contributors
The following have contributed to this page
