Computer Science Research Institute

Title: Monte Carlo Sampling in Stochastic Programming: Assessing Solution Quality and Sequential Sampling

Speaker: Güzin Bayraksan, University of Arizona and David Morton, Stanford University

Date/Time: Thursday, January 14th, 2010 from 10:30-11:30am

Location: CSRI Building, Room 90 (Sandia NM) videoconferenced to 915/W133 (Sandia CA)

Brief Abstract: We first present a simple, easily implemented procedure that uses Monte Carlo sampling to form a point and interval estimator on the optimality gap of a candidate solution to a stochastic program. We then discuss variations aimed to reduce computational effort and variance. We also provide a framework that allows the use these optimality gap estimators in an algorithmic way by providing rules to sequentially increase the sample sizes and to terminate. This scheme can be used as a stand-alone sequential sampling procedure, or it can be used in conjunction with a variety of sampling-based algorithms to obtain a solution to a stochastic program with a priori control on the quality of that solution.

Bios:
Güzin Bayraksan is an Assistant Professor of Systems and Industrial Engineering at the University of Arizona. She holds a B.S. degree in Industrial Engineering from Boğaziçi University and M.S. and Ph.D. degrees in Operations Research and Industrial Engineering from The University of Texas at Austin. Her research focuses on stochastic optimization, particularly simulation-based approximations in stochastic programming with applications in water resources management.

David Morton received his Ph.D. in Operations Research from Stanford University. He then joined the Operations Research Department at the Naval Postgraduate School as a National Research Council Postdoctoral Fellow. He is now an Engineering Foundation Professor in the Graduate Program in Operations Research and Industrial Engineering at The University of Texas at Austin. He has research interests in computational stochastic optimization, Monte Carlo approximations for stochastic programs, and interdiction modeling.

CSRI POC: Jean Paul Watson, (505) 845-8887