Stopping Rules for Class of Sampling-Based Stochastic Programming Algorithms
Morton, David P.
MetadataShow full item record
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
NPS Report NumberNPS-OR-94-003
Showing items related by title, author, creator and subject.
Armstrong, Robert Kyle (Monterey, California. Naval Postgraduate School, 1997-09);This thesis investigates, using in-line simulation, the effect of non-deterministic runtime distributions on the performance of SmartNet's schedule execution using the Opportunistic Load Balancing (OLB) Algorithm, the ...
Static-task scheduling incorporating precedence constraints and deadlines in a heterogeneous-computing environment / Michael D. Niedert. Niedert, Michael D. (Monterey, California. Naval Postgraduate School, 2000-06);Distributed systems have grown in popularity due to the rapid increase in networking of personal computers. A mixture of computers consisting of different architectures can be more powerful, reliable, and scalable than a ...
Cataldo, Edmund F. (Monterey, California: Naval Postgraduate School, 1990-09);Evaluation of the SSMI HAC precipitation algorithm is presented. SSMI rain rate data from five passes during ERICA IOP 2 and 3 were compared to all available ship observations, dropwinsonde soundings and coastal radar. ...