Abstract
Consider a network of unreliable links, each of which comes with a certain price and reliability. Given a fixed budget, which links should be bought in order to maximize the system’s reliability? We introduce a Cross-Entropy approach to this problem, which can deal effectively with the noise and constraints in this difficult combinatorial optimization problem. Numerical results demonstrate the effectiveness of the proposed technique.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press, Oxford (1987)
Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal of Computing 12, 777–787 (1982)
de Boer, P.T., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A tutorial on the crossentropy method. Annals of Operations Research 134, 19–67 (2005)
Rubinstein, R.Y., Kroese, D.P.: The Cross-Entropy Method: A unified approach to Combinatorial Optimization. In: Monte Carlo Simulation and Machine Learning. Springer, New York (2004)
Alon, G., Kroese, D.P., Raviv, T., Rubinstein, R.Y.: Application of the buffer allocation problem in simulation-based environment. Annals of Operations Research 134, 137–151 (2005)
Chepuri, K., Homem de Mello, T.: Solving the vehicle routing problem with stochastic demands using the cross-entropy method. Annals of Operations Research 134, 153–181 (2005)
Elperin, T., Gertsbakh, I.B., Lomonosov, M.: Estimation of network reliability using graph evolution models. IEEE Transactions on Reliability 40, 572–581 (1991)
Hui, K.P., Bean, N., Kraetzl, M., Kroese, D.P.: The tree cut and merge algorithm for estimation of network reliability. Probability in the Engineering and Informational Sciences 17, 24–45 (2003)
Hui, K.P., Bean, N., Kraetzl, M., Kroese, D.P.: Network reliability estimation using the tree cut and merge algorithm with importance sampling. In: Proceedings of Fourth International Workshop on Design of Reliable Communication Networks, pp. 254–262 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nariai, S., Hui, KP., Kroese, D.P. (2005). Designing an Optimal Network Using the Cross-Entropy Method. In: Gallagher, M., Hogan, J.P., Maire, F. (eds) Intelligent Data Engineering and Automated Learning - IDEAL 2005. IDEAL 2005. Lecture Notes in Computer Science, vol 3578. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11508069_30
Download citation
DOI: https://doi.org/10.1007/11508069_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26972-4
Online ISBN: 978-3-540-31693-0
eBook Packages: Computer ScienceComputer Science (R0)