Article ID: | iaor20053052 |
Country: | Netherlands |
Volume: | 134 |
Issue: | 1 |
Start Page Number: | 101 |
End Page Number: | 118 |
Publication Date: | Feb 2005 |
Journal: | Annals of Operations Research |
Authors: | Kraetzl M., Kroese Dirk P., Hui K.-P., Bean N. |
Keywords: | heuristics, programming: network, simulation |
Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network – expressed as the probability that certain nodes in the network are connected – is a computationally difficult task. In this paper we study how the Cross-Entropy method can be used to obtain more efficient network reliability estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutation Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques.