Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

Z. L. Chen, Warren Buckler Powell

Research output: Contribution to journalArticle

54 Scopus citations

Abstract

We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.

Original languageEnglish (US)
Pages (from-to)497-524
Number of pages28
JournalJournal of Optimization Theory and Applications
Volume102
Issue number3
DOIs
StatePublished - Sep 1999

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Keywords

  • Convergence with probability one
  • Cutting planes
  • Multistage stochastic programming
  • Sampling

Fingerprint Dive into the research topics of 'Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse'. Together they form a unique fingerprint.

  • Cite this