Highly Reliable Stochastic Flow Network Reliability Estimation

This state of the art discusses the problem of reliability estimation for highly reliable stochastic flow networks. There are algorithms to compute this reliability exactly, but they have exponential complexity, making the problem intractable for large or even medium sized networks. In this case Monte Carlo simulation is a simple and straightforward alternative tool to provide a reliability estimation. However, standard Monte Carlo is efficient only if the reliability is not extremely high, otherwise variance reduction techniques are required. This work explores different methods designed to reduce the variance of the estimators in this context. These methods are introduced together with a brief review of the algorithms in which they are based. Also, their precision and computational efficiency is discussed, giving some insights on their relative performance and suitability.