A NETWORK RECOURSE DECOMPOSITION METHOD FOR DYNAMIC NETWORKS WITH RANDOM ARC CAPACITIES

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. (C) 1994 John Wiley & Sons, Inc.