The "Best" Algorithm for Solving Stochastic Mixed Integer Programs / Proceedings of the 2006 Winter Simulation Conference
Loading...
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)
Organization
Naval Postgraduate School (U.S.)
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.