Monte Carlo (Importance) Sampling within a Benders Decomposition Algorithm for Stochastic Linear Programs Extended Version: Including Results of Large-Scale Problems

Abstract

The paper focuses on Benders decomposition techniques and Monte Carlo sampling (importance sampling) for solving two-stage stochastic linear programs with recourse, a method first introduced by George B. Dantzig and Peter Glynn (1990). The algorithm is discussed and further developed. The paper gives a complete presentation of the method as it is currently implemented. Numerical results from test problems of different areas are presented. Using small test problems we compare the solutions obtained by the algorithm with the universe solutions. We present the solution of large-scale problems with numerous stochastic parameters which in the deterministic equivalent formulation would have billions of constraints. The problems concern expansion planning of electric utilities with uncertainty in the availabilities of generators and transmission lines and portfolio management with uncertainty in the future return.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1991
Accession Number
ADA236419

Entities

People

  • Gerd Infanger

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Availability
  • Computational Science
  • Computations
  • Computer Programming
  • Computers
  • Decomposition
  • Generators
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Probability
  • Random Variables
  • Sampling
  • Simplex Method
  • Transmission Lines

Readers

  • Operations Research
  • Regression Analysis.