Solving a Class of Stochastic Mixed-Integer Programs With Branch and Price

Abstract

We begin this paper by identifying a class of stochastic mixed-integer programs that have column-oriented formulations suitable for solution by a branch-and-price algorithm (B&P). We then survey a number of examples, and use a stochastic facility-location problem (SFLP) for a detailed demonstration of the relevant modeling and solution techniques. Computational results with a scenario representation of uncertain costs, demands and capacities show that B&P can be orders of magnitude faster than solving the standard formulation by branch and bound. We also demonstrate how B&P can solve SFLP exactly - as exactly as a deterministic mixed-integer program - when demands and other parameters can be represented as certain types of independent, random variables, e.g., independent, normal random variables with integer means and variances.

Open PDF

Document Details

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

Entities

People

  • Eduardo F. Silva
  • R. Kevin Wood

Tags

Communities of Interest

  • Air Platforms
  • Ground and Sea Platforms
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Convex Programming
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Models
  • Mathematical Programming
  • Operations Research
  • Optimization
  • Probability
  • Probability Distributions
  • Random Variables
  • Standards

Readers

  • Marine Ecological Systems Migration
  • Operations Research
  • Statistical inference.