IDEAS home Printed from https://ideas.repec.org/p/aeg/wpaper/2010-2.html
   My bibliography  Save this paper

Solving Survivable Two-Layer Network Design Problems by Metric Inequalities

Author

Listed:
  • Sara Mattia

    (Dipartimento di Informatica e Sistemistica "Antonio Ruberti" Sapienza, Universita' di Roma)

Abstract

We address the problem of designing a multi-layer network with survivability requirements. We are given a two-layer network: the lower layer represents the potential physical connections that can be activated, the upper layer is made of logical connections that can be set up using physical links. We are given origin-destination demands (commodities) to be routed at the upper layer. We are also given a set of failure scenarios and, for every scenarios, an associated subset of commodities. The goal is to install minimum cost integer capacities on the links of both layers in order to ensure that the commodities can be routed simultaneously on the network. In addition, in every failure scenario the routing of the associated commodities must be guaranteed. We consider two variants of the problem and develop a branch-and-cut scheme based on the capacity formulation. Computational results on instances derived from the SNDLib for single node failure scenarios are discussed.

Suggested Citation

  • Sara Mattia, 2010. "Solving Survivable Two-Layer Network Design Problems by Metric Inequalities," DIS Technical Reports 2010-02, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".
    • Handle: RePEc:aeg:wpaper:2010-2
    as

    Download full text from publisher

    File URL: http://www.dis.uniroma1.it/~bibdis/RePEc/aeg/wpaper/2010-02.pdf
    File Function: First version, 2010
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Sylvie Borne & Eric Gourdin & Bernard Liau & A. Mahjoub, 2006. "Design of survivable IP-over-optical networks," Annals of Operations Research, Springer, vol. 146(1), pages 41-73, September.
    2. Luís Gouveia & Pedro Patrício & Amaro Sousa, 2008. "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM," Networks and Spatial Economics, Springer, vol. 8(1), pages 3-21, March.
    3. Knippel, Arnaud & Lardeux, Benoit, 2007. "The multi-layered network design problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 87-99, November.
    4. Geir Dahl & Alexander Martin & Mechthild Stoer, 1999. "Routing Through Virtual Paths in Layered Telecommunication Networks," Operations Research, INFORMS, vol. 47(5), pages 693-702, October.
    5. Arie M. C. A. Koster & Adrian Zymolka, 2007. "Tight LP‐based lower bounds for wavelength conversion in optical networks," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 115-136, February.
    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. Sara Mattia, 2010. "The Robust Network Loading Problem with Dynamic Routing," DIS Technical Reports 2010-03, Department of Computer, Control and Management Engineering, Universita' degli Studi di Roma "La Sapienza".

    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. Sara Mattia, 2012. "Solving survivable two-layer network design problems by metric inequalities," Computational Optimization and Applications, Springer, vol. 51(2), pages 809-834, March.
    2. Crainic, Teodor Gabriel & Gendron, Bernard & Akhavan Kazemzadeh, Mohammad Rahim, 2022. "A taxonomy of multilayer network design and a survey of transportation and telecommunication applications," European Journal of Operational Research, Elsevier, vol. 303(1), pages 1-13.
    3. Luís Gouveia & Pedro Patrício & Amaro Sousa, 2008. "Hop-Constrained Node Survivable Network Design: An Application to MPLS over WDM," Networks and Spatial Economics, Springer, vol. 8(1), pages 3-21, March.
    4. Carayannis, Elias G. & Grigoroudis, Evangelos & Wurth, Bernd, 2022. "OR for entrepreneurial ecosystems: A problem-oriented review and agenda," European Journal of Operational Research, Elsevier, vol. 300(3), pages 791-808.
    5. Alexander Veremyev & Vladimir Boginski & Eduardo Pasiliao, 2015. "Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra," Journal of Global Optimization, Springer, vol. 61(1), pages 109-138, January.
    6. 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.
    7. C S Sung & S H Song, 2003. "Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 72-82, January.
    8. Knippel, Arnaud & Lardeux, Benoit, 2007. "The multi-layered network design problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 87-99, November.
    9. Xiangyong Li & Y. P. Aneja, 2020. "A new branch-and-cut approach for the generalized regenerator location problem," Annals of Operations Research, Springer, vol. 295(1), pages 229-255, December.
    10. Hyun Kim, 2012. "P-hub protection models for survivable hub network design," Journal of Geographical Systems, Springer, vol. 14(4), pages 437-461, October.
    11. 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.
    12. BOTTON, Quentin & FORTZ, Bernard & GOUVEIA, Luis & POSS, Michael, 2011. "Benders decomposition for the hop-constrained survivable network design problem," LIDAM Discussion Papers CORE 2011037, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).

    More about this item

    Keywords

    optical network design; branch-and-cut;

    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:aeg:wpaper:2010-2. 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: Antonietta Angelica Zucconi (email available below). General contact details of provider: https://edirc.repec.org/data/dirosit.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.