Evaluate the performance of a stochastic-flow network with cost attribute in terms of minimal cuts

This paper proposes a performance index to measure the quality level of a stochastic-flow network in which each node has a designated capacity, which will have different lower levels due to various partial and complete failures. The performance index is the probability that the maximum flow of the network equals the demand d without exceeding the budget b. A simple algorithm in terms of minimal cuts is first proposed to generate all upper boundary points for (d,b), and then the probability that the maximum flow is less than or equal to d can be calculated in terms of such points. The upper boundary point for (d,b) is a maximal vector representing the capacity of each arc such that the maximum flow of the network under the budget b is d. The performance index can be calculated by repeating the proposed algorithm to obtain all upper boundary point for (d− 1,b). A benchmark example is shown to illustrate the solution procedure.