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. 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)

    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. Xiangyong Li & Y. P. Aneja, 0. "A new branch-and-cut approach for the generalized regenerator location problem," Annals of Operations Research, Springer, vol. 0, pages 1-27.
    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. 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.
    5. 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.
    6. 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.
    7. 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.

    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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: . General contact details of provider: https://edirc.repec.org/data/dirosit.html .

    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 hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.