Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Solving survivable two-layer network design problems by metric inequalities

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

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 scenario, 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Atamtürk, A.: On capacitated network design cut-set polyhedra. Math. Program. 92, 425–437 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  2. Avella, P., Mattia, S., Sassano, A.: Metric inequalities and the network loading problem. Discrete Optim. 4, 103–114 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Banerjee, D., Mukherjee, B.: Wavelength-routed optical networks: linear formulatation, resource budgeting tradeoffs, and a reconfiguration study. IEEE Trans. Netw. 8(5), 598–607 (2000)

    Article  Google Scholar 

  4. Belotti, P., Malucelli, F.: Multilayer network design: a row-column generation algorithm. In: Proceedings of the 2nd International Network Optimization Conference (INOC 2005), vol. 3, pp. 422–427. Lisbon, Portugal, March (2005)

    Google Scholar 

  5. Belotti, P., Capone, A., Carello, G., Malucelli, F., Senaldi, F., Totaro, A.: Design of multi-layer networks with traffic grooming and statistical multiplexing. In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, April (2007)

    Google Scholar 

  6. Bernard, B., Poss, M.: An improved benders decomposition applied to a multi-layer network design problem. Oper. Res. Lett. 37(5), 777–795 (2009)

    Google Scholar 

  7. Bienstock, D., Chopra, S., Günlük, O., Tsai, C.Y.: Mininum cost capacity installation for multicommodity flows. Math. Program. 81, 177–199 (1998)

    MATH  Google Scholar 

  8. Borne, S., Gourdin, E., Liau, B., Mahjoub, A.: Design of survivable IP-over-optical networks. Ann. Oper. Res. 146, 41–73 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  9. Costa, A.M., Cordeau, J.F., Gendron, B.: Metric inequalities, cutset inequalities and benders feasibility cuts for multicommodity capacitated network design. Comput. Optim. Appl. 42(3), 371–392 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Dahl, G., Martin, A., Stoer, M.: Routing through virtual paths in layered telecommunication networks. Oper. Res. 47(5), 693–702 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  11. Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Berlin (1997)

    MATH  Google Scholar 

  12. Deza, M., Pantaleeva, E.: Quasi-semi-metrics, oriented multi-cuts and related polyhedra. Eur. J. Comb. 21, 777–795 (2000)

    Article  MATH  Google Scholar 

  13. Gouveia, L., Patricio, P., de Sousa, A.: Hop-constrained node survivable network design: An application to MPLS over WDM. Netw. Spatial Econ. 8(1), 3–21 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Günlük, O.: A branch-and-cut algorithm for capacitated network design problems. Math. Program. 86, 17–39 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Iri, M.: On an extension of the max-flow min-cut theorem to multicommodity flows. J. Oper. Res. Soc. Jpn. 13, 129–135 (1971)

    MathSciNet  MATH  Google Scholar 

  16. Kerivin, H., Mahjoub, A.: Design of survivable networks: a survey. Networks 46(1), 1–21 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  17. Knippel, A., Lardeaux, B.: The multi-layered network design problem. Eur. J. Oper. Res. 183, 87–99 (2007)

    Article  MATH  Google Scholar 

  18. Koster, A.M.C.A., Zymolka, A.: Provably good solutions for wavelength assignment in optical networks. In: Proceedings of ONDM 2005, pp. 335–345. The 9th IFIP Working Conference on Optical Network Design & Modelling, Milan, Italy (2005)

    Google Scholar 

  19. Koster, A.M.C.A., Zymolka, A.: Tight LP-based lower bounds for wavelength conversion in optical networks. Stat. Neerlandica 61(1), 115–136 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  20. Koster, A., Orlowski, S., Raack, C., Baier, G., Engel, T.: Single-layer cuts for multi-layer network design problems. In: Selected Proceedings 9th INFORMS Telecommunications Conference, vol. 1, pp. 1–23. Springer, Berlin (2008)

    Google Scholar 

  21. Lomonosov, M.: Combinatorial approaches to multiflow problems. Discrete Appl. Math. 11, 1–93 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  22. Mattia, S.: The Network Loading Problem. PhD thesis, Università degli Studi di Roma “La Sapienza” (2004)

  23. Onaga, K., Kakusho, O.: On feasibility conditions of multicommodity flows in network. IEEE Trans. Circ. Theory 18(4), 425–429 (1971)

    Article  MathSciNet  Google Scholar 

  24. Orlowski, S.: Optimal design of survivable multi-layer telecommunication networks. PhD thesis, TU Berlin (2009). http://opus.kobv.de/tuberlin/volltexte/2009/2275/

  25. Orlowski, S., Koster, A., Raack, C., Wessäly, R.: Two-layer network design by branch-and-cut featuring MIP-based heuristics. In: Proceedings of the INOC 2007, Spa, Belgium (2007)

    Google Scholar 

  26. Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0–survivable network design library. In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, April (2007). http://sndlib.zib.de

    Google Scholar 

  27. Orlowski, S., Wessäly, R.: An integer programming model for multi-layer network design. ZIB Preprint ZR-04-49, Konrad-Zuse-Zentrum für Informationstechnik Berlin, December (2004). http://www.zib.de/PaperWeb/abstracts/ZR-04-49

  28. Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large scale symmetric traveling salesman problems. SIAM Rev. 33(1), 60–100 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  29. Rajan, D.: Designing capacitated survivable networks: polyhedral analysis and algorithms. PhD thesis, UC Berkeley (2004)

  30. Stoer, M., Dahl, G.: A polyhedral approach to multicommodity survivable network design. Numer. Math. 68(1) (1994)

Download references

Author information

Authors and Affiliations

  1. Fakultät für Mathematik, Technische Universität Dortmund, Dortmund, Germany

    Sara Mattia

Authors
  1. Sara Mattia
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sara Mattia.

Additional information

This paper was written while the author was a Postdoctoral Fellow at the Dipartimento di Informatica e Sistemistica “Antonio Ruberti”, Sapienza, Università di Roma.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mattia, S. Solving survivable two-layer network design problems by metric inequalities. Comput Optim Appl 51, 809–834 (2012). https://doi.org/10.1007/s10589-010-9364-0

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-010-9364-0

Keywords

Search

Navigation