Wednesday, 16:15 - 16:40 h, Room: MA 144


Rasool Tahmasbi
Network flow problems with random arc failures

Coauthor: S. Mehdi Hashemi


Networks have been widely used for modeling real-world problems such as communication, transportation, power, and water networks, which are subject to component failures. We consider stochastic network flows, in which the arcs fail with some known probabilities. In contrast to previous research that focuses on the evaluation of the expected maximum flow value in such networks, we consider the situation in which a flow must be implemented before the realization of the uncertainty. We present the concept of expected value of a given flow and seek for a flow with maximum expected value.
We show the problem of computing the expected value of a flow is NP-hard.
We examine the "value of information'', as the relative increase in the expected flow value if we allow implementing a maximum flow after the uncertainty is revealed. We show that the value of information can be around 61,% on some instances. While it is significantly hard to compute the expected maximum flow value and to determine a flow with maximum expected value, we apply a simple simulation-based method to approximate these two values. We give computational results to demonstrate the ability of this method.


Talk 3 of the contributed session Wed.3.MA 144
"Network design, reliability, and PDE constraints" [...]
Cluster 22
"Stochastic optimization" [...]


  The best way to go for you to know the credible Michigan Payday Loans providers. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.