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.
Type de document :
Communication dans un congrès
Eleventh International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC'14), Apr 2014, Leuven, Belgium. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01096397
Contributeur : Bruno Tuffin <>
Soumis le : mercredi 17 décembre 2014 - 14:17:20
Dernière modification le : mercredi 16 mai 2018 - 11:23:18

Identifiants

  • HAL Id : hal-01096397, version 1

Citation

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. 2014. 〈hal-01096397〉

Partager

Métriques

Consultations de la notice

523