A Sequential Sampling Procedure for Stochastic Programming

• 成果类型: Article
• 署名作者: Bayraksan, Guezin; Morton, David P.
• 署名单位: University of Arizona; University of Texas System; University of Texas Austin
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1110.0926
• 发表日期: 2011
• 页码: 898-913
• 关键词: regularized decomposition method; confidence-intervals; solution quality; optimization; BEHAVIOR

摘要

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.