A network recourse decomposition method for dynamic networks with random arc capacities

Warren Buckler Powell, Raymond K.‐M Cheung

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

We study a class of two‐stage dynamic networks with random arc capacities where the decisions in the first stage must be made before realizing the random quantities in the second stage. The expected total cost of the second stage is a function of the first‐stage decisions, known as the expected recourse function, which is generally intractable. This paper proposes a new method to approximate the expected recourse function as a convex, separable function of the supplies to the second stage. First, the second‐stage network is decomposed using Lagrangian relaxation into tree subproblems whose expected recourse functions are numerically tractable. Subgradient optimization is then used to update the Lagrange multipliers to improve the approximations. Numerical experiments show that this structural decomposition approach can produce high‐quality approximations of the expected recourse functions for large stochastic networks. © 1994 by John Wiley & Sons, Inc.

Original languageEnglish (US)
Pages (from-to)369-384
Number of pages16
JournalNetworks
Volume24
Issue number7
DOIs
StatePublished - Oct 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A network recourse decomposition method for dynamic networks with random arc capacities'. Together they form a unique fingerprint.

  • Cite this