Skip to Main content Skip to Navigation
Conference papers

Network reliability simulation with extension to Marshall-Olkin copula-based dependent failures

Abstract : In telecommunications, power supply systems and transportation systems, among other areas, it is of interest to compute the probability that a set of nodes is connected within a network subject to failure of edges. This can be done by considering a non-oriented graph G for which links mayfail, with probability qi for link i. Since the exact evaluation is an NP-hard problem in general with respect to the size of the graph, Monte Carlo simulation techniques are generally needed, and rare-event simulation techniques when dealing with low probabilities of disconnection. Two typesof methods can be applied, namely splitting and importance sampling. In a first part of the talk, we review our existing works on zero-variance importance sampling approximation techniques applied to this context. The methods have been applied to the context of independent failures between links. The general idea is to generate the link states one by one, using a sampling strategy that approximates an ideal zero-variance importance sampling scheme. The approximation is based on minimal cuts in subgraphs, and the relative error of the resulting estimator is shown to stay bounded as individual link failure probabilities tend to zero, and even to converge to 0 under some conditions. The method can be sped up by applying series-parallel reductions of the graph each time a link state is sampled. Another extension is to try improve the mincut-based approximation by using a convex linear combination of this approximation and a minpath-based one.In a second part of the talk, we relax the assumption of independent failures of links by the realistic Marshall-Olkin copula model for failures, so that the links can fail in groups (called shocks) with certain probabilities for the groups. We describe how, instead of sampling links sequentially, we can sample shocks sequentially, and we discuss the application of zero-variance importance sampling to this context. Depending on time, we will also present a splitting algorithm recently designed for this type of model.
Document type :
Conference papers
Complete list of metadatas
Contributor : Bruno Tuffin <>
Submitted on : Wednesday, December 17, 2014 - 2:17:20 PM
Last modification on : Monday, July 20, 2020 - 12:34:51 PM


  • HAL Id : hal-01096397, version 1


Pierre l'Ecuyer, Bruno Tuffin. Network reliability simulation with extension to Marshall-Olkin copula-based dependent failures. Eleventh International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC'14), Apr 2014, Leuven, Belgium. ⟨hal-01096397⟩



Record views