zbMATH — the first resource for mathematics

A new importance sampling Monte Carlo method for a flow network reliability problem. (English) Zbl 1142.90332
Summary: The exact evaluation of the probability that the maximum st-flow is greater than or equal to a fixed demand in a stochastic flow network is an NP-hard problem. This limitation leads one to consider Monte Carlo alternatives. In this paper, we propose a new importance sampling Monte Carlo method. It is based on a recursive use of the state space decomposition methodology of Doulliez and Jamoulle during the simulation process. We show theoretically that the resulting estimator belongs to the variance-reduction family and we give an upper bound on its variance. As shown by experimental tests, the new sampling principle offers, in many cases, substantial speedups with respect to a previous importance sampling based on the same decomposition procedure and its best performances are obtained when highly reliable networks are analyzed.

90B15 Stochastic network models in operations research
90B35 Deterministic scheduling theory in operations research
62N05 Reliability and life testing
Full Text: DOI
[1] Alexopoulos, IEEE Trans Reliab 44 pp 354– (1995)
[2] Alexopoulos, Probab Eng Inf Sci 6 pp 99– (1992)
[3] Alexopoulos, Networks 23 pp 605– (1993)
[4] Ball, IEEE Trans Reliab 35 pp 230– (1986)
[5] Cancela, IEEE Trans Reliab 47 pp 159– (1998)
[6] and Introduction to algorithms, The MIT Press, Cambridge, MA, 1990.
[7] Doulliez, RAIRO (Nov) pp 45– (1972)
[8] Direct evaluation and simulation of communication network reliability parameters. Sequential and memory distributed parallel algorithms, Ph.D. thesis, Rennes I, Campus de Beaulieu, 35042 Rennes, France, December 1992.
[9] Elperin, IEEE Trans Reliab 40 pp 572– (1991)
[10] Fishman, Nav Res Logistics 36 pp 829– (1989)
[11] Principles of discrete event digital simulation, Wiley, New York, 1978.
[12] Fishman, Probab Eng Inf Sci 3 pp 493– (1989)
[13] Ross, J Appl Math Stoch Anal 7 pp 331– (1994)
[14] Probability and statistics with reliability, queueing, and computer science applications, Prentice-Hall, Englewood Cliffs, NJ, 1982.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.