Publication:
The "Best" Algorithm for Solving Stochastic Mixed Integer Programs / Proceedings of the 2006 Winter Simulation Conference

Loading...
Thumbnail Image
Authors
Sanchez, Susan M.
Wood, R. Kevin
Subjects
Advisors
Date of Issue
2006
Date
Winter 2006
Publisher
Proceedings of the 2006 Winter Simulation Conference
Language
Abstract
We present a new algorithm for solving two-stage stochastic mixed-integer programs (SMIPs) having discrete first-stage variables, and continuous or discrete second-stage variables. For a minimizing SMIP, the BEST algorithm (1) computes an upper Bound on the optimal objective value (typically a probabilistic bound), and identifies a deterministic lowerbounding function, (2) uses the bounds to Enumerate a set of first-stage solutions that contains an optimal solution with pre-specified confidence, (3) for each first-stage solution, Simulates second-stage operations by repeatedly sampling random parameters and solving the resulting model instances, and (4) applies statistical Tests (e.g., “screening procedures”) to the simulated outcomes to identify a nearoptimal first-stage solution with pre-specified confidence. We demonstrate the algorithm’s performance on a stochastic facility-location problem.
Type
Article
Description
SUSAN M. SANCHEZ is Professor of Operations Research at the Naval Postgraduate School, where she holds a joint appointment in the Graduate School of Business and Public Policy. Her research interests include experimental design for simulation studies, data-intensive statistics, and robust selection. She has a Ph.D. in Operations Research from Cornell University. She is currently the Simulation Area Editor for the INFORMS Journal on Computing and the ASA representative to the WSC Board of Directors. Her e-mail and web addresses are and <http://www.nps.navy.mil/orfacpag/ resumePages/sanchs.htm>, respectively.
Series/Report No
Department
Operations Research (OR)
Other Units
Naval Postgraduate School, Monterey, CA.
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Proceedings of the 2006 Winter Simulation Conference L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, and R. M. Fujimoto, eds.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections