The "Best" Algorithm for Solving Stochastic Mixed Integer Programs

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 lower-bounding 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2006
Accession Number
ADA487381

Entities

People

  • R. Kevin Wood
  • Susan M. Sanchez

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Ground and Sea Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Convex Programming
  • Data Science
  • Evolutionary Algorithms
  • Information Science
  • Interdiction
  • Linear Programming
  • Monte Carlo Method
  • Operations Research
  • Optimization
  • Sampling
  • Simulations
  • Statistical Algorithms
  • Statistical Analysis
  • Statistical Tests
  • Statistics

Fields of Study

  • Mathematics

Readers

  • Computational Modeling and Simulation
  • Operations Research