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

**Rasool Tahmasbi**

Network flow problems with random arc failures

**Coauthor: S. Mehdi Hashemi**

**Abstract:**

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"** [...]