A Greedy Algorithm for Faster Feasibility Evaluation of All-Terminal-Reliable Networks

Abstract

Although calculating the all-terminal reliability (ATR) of a stochastic network is a computationally expensive task, deciding whether the ATR is greater than a preset value could be done with less effort. This study proposes a new method that generates the sequential lower and upper bounds of the ATR, based on greedy network factoring. The proposed method begins by finding the most reliable spanning tree and most unreliable cut set in the given network. Their operative and failing probabilities are used to update the lower and upper bounds of the ATR. Subnetworks are then produced, corresponding to each state of the spanning tree or cut set. This procedure is applied to the subnetworks in a recursive manner to update the ATR bounds further, until either the lower or upper bound reaches the preset ATR requirement. Due to the rapid convergence of the ATR bounds, the feasibility of a given network is likely to be decided at an early stage of the network factoring process. This study proposes several different implementations of the greedy algorithm and introduces the results of the computer experiments comparing them. Based on the experimental results, this study suggests a relationship between the performance of each implementation and the characteristics of the given network, such as layout and edge operating probabilities.