Validating Sample Average Approximation Solutions with Negatively Dependent Batches

Jiajie Chen, Cong Han Lim, Peter Z. G. Qian, Jeff Linderoth, Stephen J. WrightarXiv 2014 · DOI · arXiv

Abstract

Sample-average approximations (SAA) are a practical means of finding approximate solutions of stochastic programming problems involving an extremely large (or infinite) number of scenarios. SAA can also be used to find estimates of a lower bound on the optimal objective value of the true problem which, when coupled with an upper bound, provides confidence intervals for the true optimal objective value and valuable information about the quality of the approximate solutions. Specifically, the lower bound can be estimated by solving multiple SAA problems (each obtained using a particular sampling method) and averaging the obtained objective values. State-of-the-art methods for lower-bound estimation generate batches of scenarios for the SAA problems independently. In this paper, we describe sampling methods that produce negatively dependent batches, thus reducing the variance of the sample-averaged lower bound estimator and increasing its usefulness in defining a confidence interval for the optimal objective value. We provide conditions under which the new sampling methods can reduce the variance of the lower bound estimator, and present computational results to verify that our scheme can reduce the variance significantly, by comparison with the traditional Latin hypercube approach.

Introduction

Stochastic programming deals with optimization under uncertainty, often involving an astronomical or infinite number of possible scenarios. Since solving for every scenario is computationally infeasible, practitioners use Sample Average Approximation (SAA). In SAA, a manageable subset (a batch) of scenarios is selected to represent the underlying distribution.

To evaluate the quality of an approximate solution, an "optimality gap" is calculated. This requires an upper bound and a lower bound. While upper bounds are relatively straightforward to obtain, lower bounds are typically estimated by solving multiple independent SAA problems and averaging their results. Current state-of-the-art methods, such as Latin Hypercube (LH) sampling, treat each batch as an independent entity. This independence results in higher-than-necessary variance, requiring a large number of batches to achieve a reliable estimate.

Methods: Sliced Sampling and Negative Dependence

The core contribution of this paper is the transition from within-batch stratification to between-batch stratification. By coordinating samples across batches rather than treating them independently, the authors introduce negative dependence. If one batch samples a "high" value in a specific region, other batches are designed to sample "low" values, causing errors to cancel out upon averaging.

Two primary novel approaches are introduced:

  1. Sliced Latin Hypercube (SLH) Sampling: A large design is "sliced" into $t$ batches. Each slice is a valid LH design, but collectively they cover the sample space more uniformly.
  2. Sliced Orthogonal Array-Based LH (SOLH) Sampling: This extends the concept using orthogonal arrays to ensure that both individual variables and pairs of variables are well-stratified across batches.
A visualization of a sliced sampling design in three dimensions, where different symbols represent distinct batches coordinated to achieve negative dependence.

The authors prove that for monotonic objective functions, SLH is mathematically guaranteed to have lower variance than independent LH. For additive functions where variables do not interact strongly, the variance reduction is even more significant.

Experimental Results

The methods were evaluated using five classic stochastic programming benchmark problems: 20term (motor freight), gbd (aircraft allocation), LandS (electrical investment), ssn (telecommunications), and storm (cargo flight scheduling).

Key findings include:

  • Significant Variance Reduction: In a "newsvendor" toy problem, SLH reduced standard error by nearly two orders of magnitude compared to independent LH.
  • Benchmark Performance: On the LandS problem, the Orthogonal Array (BB) method performed 5–10x better than other sliced methods.
  • Efficiency: The computational overhead for generating these sliced samples is negligible (milliseconds) compared to the time required to solve the optimization problems (seconds to minutes).
  • Tighter Bounds: Sliced methods consistently produced lower standard errors, allowing for high-confidence results with significantly less total computation.

Conclusion

This research demonstrates that coordinating SAA batches through negative dependence provides a "free" upgrade for stochastic optimization. While proving monotonicity for complex "black-box" programs can be challenging and orthogonal arrays have rigid structural requirements, the benefits in variance reduction are substantial. Future work may involve applying these principles to randomized quasi-Monte Carlo methods to further enhance estimator precision.

Summary updated

Abstract

Sample-average approximations (SAA) are a practical means of finding approximate solutions of stochastic programming problems involving an extremely large (or infinite) number of scenarios. SAA can also be used to find estimates of a lower bound on the optimal objective value of the true problem which, when coupled with an upper bound, provides confidence intervals for the true optimal objective value and valuable information about the quality of the approximate solutions. Specifically, the lower bound can be estimated by solving multiple SAA problems (each obtained using a particular sampling method) and averaging the obtained objective values. State-of-the-art methods for lower-bound estimation generate batches of scenarios for the SAA problems independently. In this paper, we describe sampling methods that produce negatively dependent batches, thus reducing the variance of the sample-averaged lower bound estimator and increasing its usefulness in defining a confidence interval for the optimal objective value. We provide conditions under which the new sampling methods can reduce the variance of the lower bound estimator, and present computational results to verify that our scheme can reduce the variance significantly, by comparison with the traditional Latin hypercube approach.
BibTeX
@misc{chen2014validating,
  author = {Jiajie Chen and Cong Han Lim and Peter Z. G. Qian and Jeff Linderoth and Stephen J. Wright},
  title = {{Validating Sample Average Approximation Solutions with Negatively Dependent Batches}},
  year = {2014},
  eprint = {1404.7208},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1404.7208},
}
Figure