Stopping Rules for Class of Sampling-Based Stochastic Programming Algorithms

Loading...
Thumbnail Image
Authors
Morton, David P.
Subjects
Stopping Rules, Monte Carlo Sampling, Stochastic Programming
Advisors
Date of Issue
1994-01
Date
1994-01
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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
Type
Technical Report
Description
Series/Report No
Department
Operations Research
Identifiers
NPS Report Number
NPS-OR-94-003
Sponsors
National Research Council
Funder
Naval Postgraduate School, Monterey, California.
Format
NA
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections