SENSITIVITY ANALYSIS IN STOCHASTIC FLOW NETWORKS USING THE MONTE-CARLO METHOD

Consider a flow network whose nodes do not restrict flow transmission and arcs have random, discrete, and independent capacities. Let s and t be a pair of selected nodes, let LAMBDA denote the value of a maximum s-t flow, and let GAMMA denote a set of s-t cuts. Also, let F denote a set of independent joint capacity distributions with common state space. For fixed I < u, this paper develops methods for approximating the probability that I less-than-or-equal-to LAMBDA < u and the probability that a cut in GAMMA is minimum given that I less-than-or-equal-to LAMBDA < u for each distribution in F. Since these evaluations are NP-hard problems, it shows how information obtained during an iterative procedure for computing the probability that I less-than-or-equal-to LAMBDA < u can be used for designing an efficient Monte Carlo sampling plan that performs sampling at few capacity distributions and uses sampling data to estimate the probabilities of interest at each distribution in F. The set of sampling distributions is chosen by solving an uncapacitated facility location problem. The paper also describes techniques for computing confidence intervals and includes an algorithm for implementing the sampling experiment. An example illustrates the efficiency of the proposed method. This method is applicable to the computation of performance measures for networks whose elements have discrete random weights (lengths, gains, etc.) for a set of joint weight distributions with common state space. (C) 1993 by John Wiley & Sons, Inc.