Premium
Investing in arcs in a network to maximize the expected max flow
Author(s) -
Wallace Stein W.
Publication year - 1987
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.3230170108
Subject(s) - mathematical proof , flow network , convergence (economics) , mathematical optimization , simple (philosophy) , flow (mathematics) , computer science , maximum flow problem , order (exchange) , mathematics , philosophy , geometry , epistemology , finance , economics , economic growth
Consider a network with arcs subject to failures. We show how the problem of investing in new arcs in such a network in order to increase the expected max flow as much as possible can be formulated as a stochastic program with network recourse. We show how to decompose the problem, and consider both exact methods and approximations. Convergence proofs are given. We demonstrate that max flow recourse problems can be solved very efficiently, since lower and upper bounds are equally simple to evaluate.