Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1994
Accession Number
ADA278654

Entities

People

  • David P. Morton

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Asymptotic Normality
  • Collecting Methods
  • Computer Programming
  • Decomposition
  • Estimators
  • Heuristic Methods
  • Intervals
  • Linear Programming
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Probability
  • Random Variables
  • Sampling
  • Theorems

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Operations Research
  • Regression Analysis.