An Adaptive Zero-Variance Importance Sampling Approximation for Static Network Dependability Evaluation

Abstract : We propose an adaptive parameterized method to approximate the zero-variance change of measure for the evaluation of static network reliability models, with links subject to failures. The method uses two rough approximations of the unreliability function, conditional on the states of any subset of links being fixed. One of these approximations, based on mincuts, under-estimates the true unknown unreliability, whereas the other one, based on minpaths, over-estimates it. Our proposed change of measure takes a convex linear combination of the two, estimates the optimal (graph-dependent) coefficient in this combination from pilot runs, and uses the resulting conditional unreliability approximation at each step of a dynamic importance sampling algorithm. This new scheme is more general and more flexible than a previously proposed zero-variance approximation scheme, based on mincuts only, and which was shown to be robust asymptotically when unreliabilities of individual links decrease toward zero. Our numerical examples show that the new scheme is often more efficient when low unreliability comes from a large number of possible paths connecting the considered nodes rather than from small failure probabilities of the links.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2014, 45, pp.9. 〈10.1016/j.cor.2013.12.011〉
Liste complète des métadonnées

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

Identifiants

Citation

Bruno Tuffin, Samira Saggadi, Pierre L'Ecuyer. An Adaptive Zero-Variance Importance Sampling Approximation for Static Network Dependability Evaluation. Computers and Operations Research, Elsevier, 2014, 45, pp.9. 〈10.1016/j.cor.2013.12.011〉. 〈hal-01096283〉

Partager

Métriques

Consultations de la notice

354