Premium
Stochastic programs over trees with random arc capacities
Author(s) -
Powell Warren B.,
Cheung Raymond K.
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.3230240304
Subject(s) - recursion (computer science) , tree (set theory) , class (philosophy) , arc (geometry) , function (biology) , mathematical optimization , random tree , computer science , mathematics , stochastic programming , combinatorics , algorithm , artificial intelligence , geometry , motion planning , evolutionary biology , robot , biology
In this paper, we study a special class of stochastic programs where the recourse problem consists of trees with random arc capacities, which we call tree recourse. We develop an efficient procedure to obtain the expected recourse function exactly for single‐stage problems. This procedure is used in a backward recursion to find the exact expected recourse function for multistage trees. We show that for large trees n ‐stage networks can be solved more easily than can a single‐stage network with n ‐levels. We also show that the expected recourse functions for single‐stage and n ‐stage formulations of the same network can be quite similar. Finally, we illustrate the potential of using the tree recourse problems in a more general stochastic network problem. © 1994 by John Wiley & Sons, Inc.