The value of information in stochastic maximum flow problems

In this paper, we study the maximum flow problem in stochastic networks with random arc failures. We present the concept of expected value of a given flow and seek a flow whose expected value is maximum. We also introduce the concept of expected capacity of a given cut. While the expected capacity of a cut can be computed in polynomial time, we show that it is NP-hard to compute the expected value of a flow.We define the value of information in stochastic networks as the relative increase in the expected value of maximum flow if we are permitted to determine a flow after the realization of the failures in the network, rather than determining a flow before the uncertainty is revealed. We use a simulation-based approach to compute the value of information and provide some computational results to demonstrate the ability of this method. Our results show that the value of information can be around 61% on some instances.