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

Design of survivable networks with vulnerability constraints

Author

Listed:
  • Gouveia, Luis
  • Leitner, Markus

Abstract

We consider the Network Design Problem with Vulnerability Constraints (NDPVC) which simultaneously addresses resilience against failures (network survivability) and bounds on the lengths of each communication path (hop constraints). Solutions to the NDPVC are subgraphs containing a path of length at most Hst for each commodity {s, t} and a path of length at most Hst′ between s and t after at most k−1 edge failures. We first show that a related and well known problem from the literature, the Hop-Constrained Survivable Network Design Problem (kHSNDP), that addresses the same two measures produces solutions that are too conservative in the sense that they might be too expensive in practice or may even fail to provide feasible solutions. We also explain that the reason for this difference is that Mengerian-like theorems not hold in general when considering hop-constraints. Three graph theoretical characterizations of feasible solutions to the NDPVC are derived and used to propose integer linear programming formulations. In a computational study we compare these alternatives with respect to the lower bounds obtained from the corresponding linear programming relaxations and their capability of solving instances to proven optimality. In addition, we show that in many cases, the solutions produced by solving the NDPVC are cheaper than those obtained by the related kHSNDP.

Suggested Citation

  • Gouveia, Luis & Leitner, Markus, 2017. "Design of survivable networks with vulnerability constraints," European Journal of Operational Research, Elsevier, vol. 258(1), pages 89-103.
    • Handle: RePEc:eee:ejores:v:258:y:2017:i:1:p:89-103
    DOI: 10.1016/j.ejor.2016.09.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716307172
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.09.003?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
    ---><---

    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. Anantaram Balakrishnan & Thomas L. Magnanti & Prakash Mirchandani, 1994. "Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem," Management Science, INFORMS, vol. 40(7), pages 846-867, July.
    2. Quentin Botton & Bernard Fortz & Luis Gouveia & Michael Poss, 2013. "Benders Decomposition for the Hop-Constrained Survivable Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 13-26, February.
    3. Luis Gouveia, 1998. "Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 180-188, May.
    4. Luis Gouveia & Pedro Patrício & Amaro Sousa, 2016. "Lexicographical minimization of routing hops in hop-constrained node survivable networks," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 62(2), pages 417-434, June.
    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. Gouveia, Luis & Leitner, Markus & Ruthmair, Mario, 2017. "Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 908-928.
    2. Yajun Lu & Hosseinali Salemi & Balabhaskar Balasundaram & Austin Buchanan, 2022. "On Fault-Tolerant Low-Diameter Clusters in Graphs," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3181-3199, November.

    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. Okan Arslan & Ola Jabali & Gilbert Laporte, 2020. "A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 120-134, January.
    2. 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.
    3. De Boeck, Jérôme & Fortz, Bernard, 2018. "Extended formulation for hop constrained distribution network configuration problems," European Journal of Operational Research, Elsevier, vol. 265(2), pages 488-502.
    4. Chardy, M. & Costa, M.-C. & Faye, A. & Trampont, M., 2012. "Optimizing splitter and fiber location in a multilevel optical FTTH network," European Journal of Operational Research, Elsevier, vol. 222(3), pages 430-440.
    5. Juan Ma & Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Vladimir Boginski, 2016. "The Minimum Spanning k -Core Problem with Bounded CVaR Under Probabilistic Edge Failures," INFORMS Journal on Computing, INFORMS, vol. 28(2), pages 295-307, May.
    6. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    7. Clavijo López, Christian & Crama, Yves & Pironet, Thierry & Semet, Frédéric, 2024. "Multi-period distribution networks with purchase commitment contracts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 556-572.
    8. Masashi Miyagawa, 2009. "Optimal hierarchical system of a grid road network," Annals of Operations Research, Springer, vol. 172(1), pages 349-361, November.
    9. Filippi, C. & Guastaroba, G. & Speranza, M.G., 2021. "On single-source capacitated facility location with cost and fairness objectives," European Journal of Operational Research, Elsevier, vol. 289(3), pages 959-974.
    10. Vatsa, Amit Kumar & Jayaswal, Sachin, 2015. "A New Formulation and Benders' Decomposition for Multi-period facility Location Problem with Server Uncertainty," IIMA Working Papers WP2015-02-07, Indian Institute of Management Ahmedabad, Research and Publication Department.
    11. Jyotirmoy Dalal & Halit Üster, 2018. "Combining Worst Case and Average Case Considerations in an Integrated Emergency Response Network Design Problem," Transportation Science, INFORMS, vol. 52(1), pages 171-188, January.
    12. 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.
    13. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    14. Vatsa, Amit Kumar & Jayaswal, Sachin, 2016. "A new formulation and Benders decomposition for the multi-period maximal covering facility location problem with server uncertainty," European Journal of Operational Research, Elsevier, vol. 251(2), pages 404-418.
    15. Costa, Alysson M. & França, Paulo M. & Lyra Filho, Christiano, 2011. "Two-level network design with intermediate facilities: An application to electrical distribution systems," Omega, Elsevier, vol. 39(1), pages 3-13, January.
    16. Gouveia, Luis, 1996. "Multicommodity flow models for spanning trees with hop constraints," European Journal of Operational Research, Elsevier, vol. 95(1), pages 178-190, November.
    17. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    18. 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).
    19. Gouveia, Luis & Leitner, Markus & Ruthmair, Mario, 2017. "Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem," European Journal of Operational Research, Elsevier, vol. 262(3), pages 908-928.
    20. Agarwal, Y.K. & Aneja, Y.P., 2017. "Fixed charge multicommodity network design using p-partition facets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 124-135.

    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:258:y:2017:i:1:p:89-103. 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.