Stopping rules for class of sampling-based stochastic programming algorithms
By: David P. Morton
Contributors: Naval Postgraduate School (U.S.). Dept. of Operations Research
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1994
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 24
Subjects: LINEAR PROGRAMMING; STOPPING RULES(MATHEMATICS)
Other titles: NPS-OR-94-003.
Description: Decomposition and Monte Carlo sampling-based algorithms hold much promise for      solving stochastic programs with many scenarios. A critical component of such algorithms      is a stopping criterion to ensure the quality of the solution. In this paper, we develop a      stopping rule theory for a class of algorithms that estimate bounds on the optimal      objective function value by sampling. We provide rules for selecting sample sizes and      terminating the algorithm under which asymptotic validity of confidence intervals for the      quality of the proposed solution can be verified. These rules are applied to a multistage      stochastic linear programming algorithm due to Pereira and Pinto. Stopping rules, Monte      Carlo sampling, Stochastic programming.
Notes: Title from cover.

"NPS-OR-94-003."

"January 1994."

AD A278 654.

Includes bibliographical references (p. 22-23).

aq/aq cc:9116 07/14/98