Robust Implementation of Permutation Monte Carlo for Network Reliability Estimation

Network reliability computation is an NP-hard problem which has attracted much attention in literature. This problem consists in, given a network where the links may fail or operate with known probabilities, to compute the probability that a given subset of nodes (known as terminals) are connected by the operational links. Given the difficulty to compute the exact value of the network reliability, an alternative which has been much explored in the literature is the use of Monte Carlo estimation methods. In this work, we discuss the Permutation Monte Carlo method, which is an estimation algorithm which has shown much promise but that is prone to numerical problems in the case of networks with a large number of links. We discuss this situation and we present a simple way to rewrite the algorithm's computations which is more numerically stable. We present some computational results showing that the method is more efficient that the standard Monte Carlo method for highly reliable networks, and that it can be applied to topologies with hundreds of links.