A combined deterministic and sampling-based sequential bounding method for stochastic programming

Péguy Pierre-Louis*, Güzin Bayraksan, David P. Morton

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

We develop an algorithm for two-stage stochastic programming with a convex second stage program and with uncertainty in the right-hand side. The algorithm draws on techniques from bounding and approximation methods as well as sampling-based approaches. In particular, we sequentially refine a partition of the support of the random vector and, through Jensen's inequality, generate deterministically valid lower bounds on the optimal objective function value. An upper bound estimator is formed through a stratified Monte Carlo sampling procedure that includes the use of a control variate variance reduction scheme. The algorithm lends itself to a stopping rule theory that ensures an asymptotically valid confidence interval for the quality of the proposed solution. Computational results illustrate our approach.

Original languageEnglish (US)
Title of host publicationProceedings of the 2011 Winter Simulation Conference, WSC 2011
Pages4167-4178
Number of pages12
DOIs
StatePublished - 2011
Event2011 Winter Simulation Conference, WSC 2011 - Phoenix, AZ, United States
Duration: Dec 11 2011Dec 14 2011

Publication series

NameProceedings - Winter Simulation Conference
ISSN (Print)0891-7736

Other

Other2011 Winter Simulation Conference, WSC 2011
CountryUnited States
CityPhoenix, AZ
Period12/11/1112/14/11

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'A combined deterministic and sampling-based sequential bounding method for stochastic programming'. Together they form a unique fingerprint.

Cite this