Maximal expected flow in a network subject to arc failures
✍ Scribed by Y. P. Aneja; K. P. K. Nair
- Publisher
- John Wiley and Sons
- Year
- 1980
- Tongue
- English
- Weight
- 494 KB
- Volume
- 10
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
In a network subject to arc failures, each chain has a probability of failure. Therefore the maximal flow in the network is a random variable. The problem considered here is that of maximizing the expected flow. An arc‐chain formulation of the problem, and an algorithm for computing an optimal solution are provided. The algorithm involves a column generation technique, and a constrained chain in the network provides a desired column at each step of the simplex algorithm. The technique presented here is an extension of that of Ford and Fulkerson. The algorithm is validated, and a geometric interpretation is included.