A sequential sampling procedure for stochastic programming

Güzin Bayraksan*, David P. Morton

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

We develop a sequential sampling procedure for a class of stochastic programs. We assume that a sequence of feasible solutions with an optimal limit point is given as input to our procedure. Such a sequence can be generated by solving a series of sampling problems with increasing sample size, or it can be found by any other viable method. Our procedure estimates the optimality gap of a candidate solution from this sequence. If the point estimate of the optimality gap is sufficiently small according to our termination criterion, then we stop. Otherwise, we repeat with the next candidate solution from the sequence under an increased sample size. We provide conditions under which this procedure (i) terminates with probability one and (ii) terminates with a solution that has a small optimality gap with a prespecified probability.

Original languageEnglish (US)
Pages (from-to)898-913
Number of pages16
JournalOperations Research
Volume59
Issue number4
DOIs
StatePublished - Jul 1 2011

Keywords

  • Programming: stochastic
  • Simulation: efficiency
  • Statistics: sampling

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A sequential sampling procedure for stochastic programming'. Together they form a unique fingerprint.

Cite this