Monte Carlo bounding techniques for determining solution quality in stochastic programs

Monte Carlo bounding techniques for determining solution quality in stochastic programs

0.00 Avg rating0 Votes
Article ID: iaor20003857
Country: Netherlands
Volume: 24
Issue: 1/2
Start Page Number: 47
End Page Number: 56
Publication Date: Feb 1999
Journal: Operations Research Letters
Authors: , ,
Keywords: programming: probabilistic
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 &xcrcmflx; to SP, e.g., = 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.

Reviews

Required fields are marked *. Your email address will not be published.