Premium
A network recourse decomposition method for dynamic networks with random arc capacities
Author(s) -
Powell Warren B.,
Cheung Raymond K.M.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240703
Subject(s) - subgradient method , mathematical optimization , function (biology) , lagrangian relaxation , relaxation (psychology) , stochastic programming , separable space , computer science , decomposition , class (philosophy) , arc (geometry) , lagrange multiplier , decomposition method (queueing theory) , mathematics , discrete mathematics , mathematical analysis , ecology , evolutionary biology , artificial intelligence , biology , geometry , psychology , social psychology
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.