G. Bayraksan; "Monte Carlo Sampling-Based Methods for..", 5.1.2005
“Monte Carlo Sampling-Based Methods for Assessing Solution Quality in Stochastic Programs”
by
Güzin Bayraksan
ORIE, The University of Texas at Austin
University Station, TX, USA.
Abstract: Determining whether a solution is of high quality (optimal or near optimal) is a fundamental question in optimization. We develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure and then present a result that justifies a computationally simplified single-replication procedure. Even though the single replication procedure is computationally
significantly less demanding, the resulting confidence interval may have low coverage probability for small sample sizes on some problems. We provide variants of this procedure that require two replications instead of one and that perform empirically better. We also provide preliminary guidelines for selecting a candidate solution to improve the procedures' performance.
Biography: Guzin Bayraksan holds a BS degree in Industrial Engineering from Bogazici
University, and an MS degree in Operations Research and Industrial Engineering
from the University of Texas at Austin. She is currently working towards a PhD
in Operations Research at the University of Texas-Austin. Before resuming her
PhD studies, she worked at United Airlines and was involved in a large-scale
credit card optimization project with Bank of America.