Title :
Graph reductions to speed up importance sampling-based static reliability estimation
Author :
L´Ecuyer, Pierre ; Saggadi, Samira ; Tuffin, Bruno
Author_Institution :
DIRO, Univ. de Montreal, Montreal, QC, Canada
Abstract :
We speed up the Monte Carlo simulation of static graph reliability models by adding graph reductions to zero-variance importance sampling (ZVIS) approximation techniques. ZVIS approximation samples the status of links sequentially, and at each step we check if series-parallel reductions can be performed. We present two variants of the algorithm and describe their respective advantages. We show that the method satisfies robustness properties as the reliability of links increases. We illustrate theoretically on small examples and numerically on large ones the gains that can be obtained, both in terms of variance and computational time.
Keywords :
Monte Carlo methods; graph theory; reliability theory; sampling methods; Monte Carlo simulation; graph reductions; importance sampling based static reliability estimation; series-parallel reductions; static graph reliability models; zero variance importance sampling approximation techniques; Approximation algorithms; Approximation methods; Joining processes; Merging; Monte Carlo methods; Reliability; Topology;
Conference_Titel :
Simulation Conference (WSC), Proceedings of the 2011 Winter
Conference_Location :
Phoenix, AZ
Print_ISBN :
978-1-4577-2108-3
Electronic_ISBN :
0891-7736
DOI :
10.1109/WSC.2011.6147770