Monte Carlo Bounding Techniques for Determining Solution Quality in Stochastic Programs

Abstract

A stochastic program SP with solution value z(exp *) can be approximately solved by sampling n realizations of the program's stochastic parameters, and by solving the resulting \approximating problem" for (x(exp *)(sub n), z(exp *)(sub n)). We show that, in expectation, z(exp *)(sub n) is a lower bound on z(exp *) and that this bound monotonically improves as n increases. The first result is used to construct confidence intervals on the optimality gap for any candidate solution ^x to SP, e.g., ^ x = x(exp *)(sub n). A sampling procedure based on common random numbers ensures nonnegative gap estimates and provides significant variance reduction over naive sampling on four test problems.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1999
Accession Number
ADA487332

Entities

People

  • David P. Morton
  • R. Kevin Wood
  • Wai-kei Mak

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Asymptotic Normality
  • Central Processing Units
  • Computer Science
  • Convergence
  • Decomposition
  • Discrete Distribution
  • Electric Power
  • Estimators
  • Intervals
  • Linear Programming
  • Observation
  • Operations Research
  • Random Variables
  • Sampling
  • Standards

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Analytical Mechanics
  • Statistical inference.