The "Best" Algorithm for Solving Stochastic Mixed Integer Programs / Proceedings of the 2006 Winter Simulation Conference
Sanchez, Susan M.
Wood, R. Kevin
MetadataShow full item record
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.
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 <firstname.lastname@example.org> and <http://www.nps.navy.mil/orfacpag/ resumePages/sanchs.htm>, respectively.
Rightsdefined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Showing items related by title, author, creator and subject.
Rhoden, Christopher A. (Monterey, California. Naval Postgraduate School, 1994-06);The Simplex algorithm, developed by George B. Dantzig in 1947 represents a quantum leap in the ability of applied scientists to solve complicated linear optimization problems. Subsequently, its utility in solving finite ...
Schwartz, Victor Scott (Monterey, California. Naval Postgraduate School, 1998-09-01);A dynamic platform-independent solver is developed for use with network and graph algorithms of operations research. This solver allows analysts to solve a large variety of problems without writing code. Algorithms from a ...
Smith, Douglas R. (Monterey, California. Naval Postgraduate School, 1979-11); NPS-52-79-004Many important problems in operations research, artificial intelligence, combinatorial algorithms, and other areas seem to require search in order to find an optimal solution. A branch and bound procedure, which imposes a ...