CHARACTERIZING STOCHASTIC FLOW NETWORKS USING THE MONTE-CARLO METHOD

Consider a flow network G = (V,E) with node set V and arc set E = {1,...,e}. Assume that the nodes do not restrict flow transmission and the arcs have random, discrete and independent capacities B1,...,B(e), and let B = {B1,...,B(e)}. Also, let s and t be a pair of nodes in V, let LAMBDA(B) denote the value of a maximum s-t flow, and let GAMMA-denote a set of s-t cuts. This work describes a highly efficient Monte Carlo sampling plan for estimating the probability that l < LAMBDA(B) less-than-or-equal-to u, the probability that a cut in GAMMA is critical and l < LAMBDA(B) less-than-or-equal-to u, and the probability that a cut in GAMMA is critical, given that l < LAMBDA(B) less-than-or-equal-to u. The proposed method takes advantage of an easily computed upper bound on the probability that l < LAMBDA(B) less-than-or-equal-to u, which is a function of both l and u to gain its computational advantage. The article also describes techniques for computing confidence intervals that are valid for any sample size. Algorithms for implementing the proposed sampling experiment are included, and an example illustrates the efficiency of the proposed method.