Cut sharing for multistage stochastic linear programs with interstage dependency

Gerd Infanger*, David P. Morton

*Corresponding author for this work

Research output: Contribution to journalArticle

101 Scopus citations

Abstract

Multistage stochastic programs with interstage independent random parameters have recourse functions that do not depend on the state of the system. Decomposition-based algorithms can exploit this structure by sharing cuts (outer-linearizations of the recourse function) among different scenario subproblems at the same stage. The ability to share cuts is necessary in practical implementations of algorithms that incorporate Monte Carlo sampling within the decomposition scheme. In this paper, we provide methodology for sharing cuts in decomposition algorithms for stochastic programs that satisfy certain interstage dependency models. These techniques enable sampling-based algorithms to handle a richer class of multistage problems, and may also be used to accelerate the convergence of exact decomposition algorithms.

Original languageEnglish (US)
Pages (from-to)241-256
Number of pages16
JournalMathematical Programming, Series B
Volume75
Issue number2
DOIs
StatePublished - Nov 30 1996

Keywords

  • Decomposition algorithms
  • Interstage dependency
  • Monte Carlo sampling
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Cut sharing for multistage stochastic linear programs with interstage dependency'. Together they form a unique fingerprint.

  • Cite this