IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v43y1995i6p1012-1024.html
   My bibliography  Save this article

Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements

Author

Listed:
  • M. Grötschel

    (Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin, Germany)

  • C. L. Monma

    (Bellcore, Morristown, New Jersey)

  • M. Stoer

    (Telenor Research and Development, Kjeller, Norway)

Abstract

We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain “two-connected” survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements, which shows promise for providing good solutions to these difficult problems.

Suggested Citation

  • M. Grötschel & C. L. Monma & M. Stoer, 1995. "Polyhedral and Computational Investigations for Designing Communication Networks with High Survivability Requirements," Operations Research, INFORMS, vol. 43(6), pages 1012-1024, December.
    • Handle: RePEc:inm:oropre:v:43:y:1995:i:6:p:1012-1024
    DOI: 10.1287/opre.43.6.1012
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.43.6.1012
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.43.6.1012?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. Yongjia Song & Minjiao Zhang, 2015. "Chance‐constrained multi‐terminal network design problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(4), pages 321-334, June.
    2. Flippo, Olaf E. & Kolen, Antoon W. J. & Koster, Arie M. C. A. & van de Leensel, Robert L. M. J., 2000. "A dynamic programming algorithm for the local access telecommunication network expansion problem," European Journal of Operational Research, Elsevier, vol. 127(1), pages 189-202, November.
    3. Naga V. C. Gudapati & Enrico Malaguti & Michele Monaci, 2022. "Network Design with Service Requirements: Scaling-up the Size of Solvable Problems," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2571-2582, September.
    4. Laporte, G. & Mesa, J.A. & Ortega, F.A. & Perea, F., 2011. "Planning rapid transit networks," Socio-Economic Planning Sciences, Elsevier, vol. 45(3), pages 95-104, September.
    5. Bhatt, Sneha Dhyani & Sinha, Ankur & Jayaswal, Sachin, 2024. "The capacitated r-hub interdiction problem with congestion: Models and solution approaches," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    6. Kennington, Jeffery L. & Olinick, Eli V. & Spiride, Gheorghe, 2007. "Basic mathematical programming models for capacity allocation in mesh-based survivable networks," Omega, Elsevier, vol. 35(6), pages 629-644, December.
    7. Shouvanik Chakrabarti & Pierre Minssen & Romina Yalovetzky & Marco Pistoia, 2022. "Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms," Papers 2210.03210, arXiv.org.
    8. Ljubić, Ivana & Mutzel, Petra & Zey, Bernd, 2017. "Stochastic survivable network design problems: Theory and practice," European Journal of Operational Research, Elsevier, vol. 256(2), pages 333-348.
    9. Garg, Manish & Smith, J. Cole, 2008. "Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios," Omega, Elsevier, vol. 36(6), pages 1057-1071, December.
    10. Anantaram Balakrishnan & Prakash Mirchandani & Harihara Prasad Natarajan, 2009. "Connectivity Upgrade Models for Survivable Network Design," Operations Research, INFORMS, vol. 57(1), pages 170-186, February.
    11. van de Leensel, R.L.J.M. & Flippo, O.E. & Koster, Arie M.C.A. & Kolen, A.W.J., 1996. "A dynamic programming algorithm for the local access network expansion problem," Research Memorandum 027, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    12. Lawrence V. Snyder & Mark S. Daskin, 2005. "Reliability Models for Facility Location: The Expected Failure Cost Case," Transportation Science, INFORMS, vol. 39(3), pages 400-416, August.
    13. Abdullah Konak & Alice E. Smith, 2011. "Efficient Optimization of Reliable Two-Node Connected Networks: A Biobjective Approach," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 430-445, August.

    More about this item

    Keywords

    forthcoming;

    Statistics

    Access and download statistics

    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:inm:oropre:v:43:y:1995:i:6:p:1012-1024. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.