Solving implementation issues of Permutation Monte Carlo in different network reliability contexts

Abstract

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 Permutation Monte Carlo, a highly efficient network reliability estimation method. The method is prone to numerical limitations for networks with a high number of links. We discuss this situation and present a simple way to rewrite the algorithm's calculations to make it numerically more stable. We also present a variant of Permutation Monte Carlo implementation for the particular case where all the links in the network under study share the same failure probability distribution (homogeneous network). For this type of network the Permutation Monte Carlo implementation can be redesigned to be much more efficient. We present some experimental test results proving that both proposed implementation variants are extremely efficient.