Monte Carlo bounding techniques for determining solution quality in stochastic programs

Wai Kei Mak, David P. Morton, R. Kevin Wood

Research output: Contribution to journalArticlepeer-review

332 Scopus citations

Abstract

A stochastic program SP with solution value z* can be approximately solved by sampling n realizations of the program's stochastic parameters, and by solving the resulting `approximating problem' for (x*n, z*n). We show that, in expectation, z*n is a lower bound on z* 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*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.

Original languageEnglish (US)
Pages (from-to)47-56
Number of pages10
JournalOperations Research Letters
Volume24
Issue number1
DOIs
StatePublished - Feb 1999

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Monte Carlo bounding techniques for determining solution quality in stochastic programs'. Together they form a unique fingerprint.

Cite this