IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v199y2009i2p542-552.html
   My bibliography  Save this article

A cross entropy approach to design of reliable networks

Author

Listed:
  • Altiparmak, Fulya
  • Dengiz, Berna

Abstract

One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks.

Suggested Citation

  • Altiparmak, Fulya & Dengiz, Berna, 2009. "A cross entropy approach to design of reliable networks," European Journal of Operational Research, Elsevier, vol. 199(2), pages 542-552, December.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:2:p:542-552
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)01011-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. G. Alon & D. Kroese & T. Raviv & R. Rubinstein, 2005. "Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based Environment," Annals of Operations Research, Springer, vol. 134(1), pages 137-151, February.
    2. Ramirez-Marquez, José Emmanuel & Rocco, Claudio M., 2008. "All-terminal network reliability optimization via probabilistic solution discovery," Reliability Engineering and System Safety, Elsevier, vol. 93(11), pages 1689-1697.
    3. Levitin, Gregory, 2003. "Optimal allocation of multi-state elements in linear consecutively connected systems with vulnerable nodes," European Journal of Operational Research, Elsevier, vol. 150(2), pages 406-419, October.
    4. Zhao, Ruiqing & Liu, Baoding, 2004. "Redundancy optimization problems with uncertainty of combining randomness and fuzziness," European Journal of Operational Research, Elsevier, vol. 157(3), pages 716-735, September.
    5. Krishna Chepuri & Tito Homem-de-Mello, 2005. "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 153-181, February.
    6. Long, Q. & Xie, M. & Ng, S.H. & Levitin, Gregory, 2008. "Reliability analysis and optimization of weighted voting systems with continuous states input," European Journal of Operational Research, Elsevier, vol. 191(1), pages 240-252, November.
    7. G Zhou & M Gen, 2003. "A genetic algorithm approach on tree-like telecommunication network design problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(3), pages 248-254, March.
    8. Pieter-Tjerk de Boer & Dirk Kroese & Shie Mannor & Reuven Rubinstein, 2005. "A Tutorial on the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 19-67, February.
    9. Chu, Chao-Hsien & Premkumar, G. & Chou, Hsinghua, 2000. "Digital data networks design using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 127(1), pages 140-158, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fahimnia, Behnam & Sarkis, Joseph & Eshragh, Ali, 2015. "A tradeoff model for green supply chain planning:A leanness-versus-greenness analysis," Omega, Elsevier, vol. 54(C), pages 173-190.
    2. Bekiros, Stelios & Nguyen, Duc Khuong & Sandoval Junior, Leonidas & Uddin, Gazi Salah, 2017. "Information diffusion, cluster formation and entropy-based network dynamics in equity and commodity markets," European Journal of Operational Research, Elsevier, vol. 256(3), pages 945-961.
    3. Saghaei, Mahsa & Ghaderi, Hadi & Soleimani, Hamed, 2020. "Design and optimization of biomass electricity supply chain with uncertainty in material quality, availability and market demand," Energy, Elsevier, vol. 197(C).
    4. Ji, Qiang & Bouri, Elie & Roubaud, David & Kristoufek, Ladislav, 2019. "Information interdependence among energy, cryptocurrency and major commodity markets," Energy Economics, Elsevier, vol. 81(C), pages 1042-1055.
    5. Fahimnia, Behnam & Sarkis, Joseph & Choudhary, Alok & Eshragh, Ali, 2015. "Tactical supply chain planning under a carbon tax policy scheme: A case study," International Journal of Production Economics, Elsevier, vol. 164(C), pages 206-215.
    6. Ji, Qiang & Marfatia, Hardik & Gupta, Rangan, 2018. "Information spillover across international real estate investment trusts: Evidence from an entropy-based network analysis," The North American Journal of Economics and Finance, Elsevier, vol. 46(C), pages 103-113.
    7. Huynh, Toan Luu Duc & Nasir, Muhammad Ali & Vo, Xuan Vinh & Nguyen, Thong Trung, 2020. "“Small things matter most”: The spillover effects in the cryptocurrency market and gold as a silver bullet," The North American Journal of Economics and Finance, Elsevier, vol. 54(C).
    8. Ferreira, Paulo & Almeida, Dora & Dionísio, Andreia & Bouri, Elie & Quintino, Derick, 2022. "Energy markets – Who are the influencers?," Energy, Elsevier, vol. 239(PA).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Enlu Zhou & Shalabh Bhatnagar, 2018. "Gradient-Based Adaptive Stochastic Search for Simulation Optimization Over Continuous Space," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 154-167, February.
    2. Xing, Liudong & Levitin, Gregory, 2018. "Connectivity modeling and optimization of linear consecutively connected systems with repairable connecting elements," European Journal of Operational Research, Elsevier, vol. 264(2), pages 732-741.
    3. Pieter-Tjerk de Boer & Dirk Kroese & Shie Mannor & Reuven Rubinstein, 2005. "A Tutorial on the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 19-67, February.
    4. Qiu, Qingan & Cui, Lirong & Gao, Hongda & Yi, He, 2018. "Optimal allocation of units in sequential probability series systems," Reliability Engineering and System Safety, Elsevier, vol. 169(C), pages 351-363.
    5. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    6. Rocco S, Claudio M. & Ramirez-Marquez, José Emmanuel, 2009. "Deterministic network interdiction optimization via an evolutionary approach," Reliability Engineering and System Safety, Elsevier, vol. 94(2), pages 568-576.
    7. Deck, Cary & Sheremeta, Roman M., 2019. "The tug-of-war in the laboratory," European Journal of Political Economy, Elsevier, vol. 60(C).
    8. Wu, Liusan & Tan, Qingmei & Zhang, Yuehui, 2013. "Network connectivity entropy and its application on network connectivity reliability," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(21), pages 5536-5541.
    9. Cortés, Pablo & Muñuzuri, Jesús & Guadix, José & Onieva, Luis, 2013. "Optimal algorithm for the demand routing problem in multicommodity flow distribution networks with diversification constraints and concave costs," International Journal of Production Economics, Elsevier, vol. 146(1), pages 313-324.
    10. Xi Chen & Enlu Zhou, 2015. "Population model-based optimization," Journal of Global Optimization, Springer, vol. 63(1), pages 125-148, September.
    11. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    12. K.-P. Hui & N. Bean & M. Kraetzl & Dirk Kroese, 2005. "The Cross-Entropy Method for Network Reliability Estimation," Annals of Operations Research, Springer, vol. 134(1), pages 101-118, February.
    13. Lvyang Qiu & Shuyu Li & Yunsick Sung, 2021. "3D-DCDAE: Unsupervised Music Latent Representations Learning Method Based on a Deep 3D Convolutional Denoising Autoencoder for Music Genre Classification," Mathematics, MDPI, vol. 9(18), pages 1-17, September.
    14. Akimoto, Youhei & Auger, Anne & Hansen, Nikolaus, 2022. "An ODE method to prove the geometric convergence of adaptive stochastic algorithms," Stochastic Processes and their Applications, Elsevier, vol. 145(C), pages 269-307.
    15. Anastasia Spiliopoulou & Ioannis Papamichail & Markos Papageorgiou & Yannis Tyrinopoulos & John Chrysoulakis, 2017. "Macroscopic traffic flow model calibration using different optimization algorithms," Operational Research, Springer, vol. 17(1), pages 145-164, April.
    16. Deng, Xiangtian & Zhang, Yi & Jiang, Yi & Zhang, Yi & Qi, He, 2024. "A novel operation method for renewable building by combining distributed DC energy system and deep reinforcement learning," Applied Energy, Elsevier, vol. 353(PB).
    17. Zhang, Yali & Shang, Pengjian, 2019. "Multivariate multiscale distribution entropy of financial time series," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 72-80.
    18. Yeh, Wei-Chang, 2017. "Evaluation of the one-to-all-target-subsets reliability of a novel deterioration-effect acyclic multi-state information network," Reliability Engineering and System Safety, Elsevier, vol. 166(C), pages 132-137.
    19. Fahimnia, Behnam & Sarkis, Joseph & Eshragh, Ali, 2015. "A tradeoff model for green supply chain planning:A leanness-versus-greenness analysis," Omega, Elsevier, vol. 54(C), pages 173-190.
    20. Chi Zhang & Jose Ramirez-Marquez, 2013. "Protecting critical infrastructures against intentional attacks: a two-stage game with incomplete information," IISE Transactions, Taylor & Francis Journals, vol. 45(3), pages 244-258.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:199:y:2009:i:2:p:542-552. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.