The "Best" Algorithm for Solving Stochastic Mixed Integer Programs / Proceedings of the 2006 Winter Simulation Conference
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.
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 <ssanchez@nps.edu>
and <http://www.nps.navy.mil/orfacpag/
resumePages/sanchs.htm>, respectively.
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Linear optimization and image reconstruction
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 ... -
Dynamic platform-independent meta-algorithms for graph-partitioning
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 ... -
On the computational complexity of branch and bound search strategies
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 ...