Skip to main content
SpringerLink
Log in

The robust network loading problem with dynamic routing

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

Abstract

In this paper the Robust Network Loading problem with splittable flows and dynamic routing under polyhedral uncertainty for the demands is considered. Polyhedral results for the capacity formulation of the problem are given. The first exact approach for solving the problem is presented. A branch-and-cut algorithm based on the proposed capacity formulation is developed. Computational results using the hose polyhedron to model the demand uncertainty 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

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Agarwal, Y.: K-partition-based facets of the network design problem. Networks 47(3), 123–139 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Altın, A., Amaldi, E., Belotti, P., Pınar, M.Ç.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1), 100–115 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Altın, A., Yaman, H., Pınar, M.Ç.: The robust network loading problem under hose demand uncertainty: formulation, polyhedral analysis, and computations. INFORMS J. Comput. 23(1), 75–89 (2010)

    Article  Google Scholar 

  4. Atamturk, A., Zhang, M.: Two-stage robust network flow and design under demand uncertainty. Oper. Res. 55, 662–673 (2007)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  6. Barahona, F.: Network design using cut inequalities. SIAM J. Optim. 6, 823–834 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Ben-Ameur, W., Kerivin, H.: Routing of uncertain traffic demands. Optim. Eng. 6, 283–313 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program., Ser. B 98, 49–71 (2003)

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  10. Chekuri, C., Oriolo, G., Scutellà, M.G., Shepherd, F.B.: Hardness of robust network design. Networks 50(1), 50–154 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chopra, S., Rao, M.R.: The steiner tree problem I: formulations, compositions and extensions of facets. Math. Program. 64, 209–229 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  12. Colson, B., Marcotte, P., Savard, G.: Bilevel programming: a survey. 4OR 3, 87–107 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  13. CPLEX. http://www.ibm.com/software/integration/optimization/cplex-optimizer/

  14. Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints. Optimization 52, 333–359 (2003)

    Article  MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  16. Duffield, N.G., Goyal, P., Greenberg, A., Mishra, P., Ramakrishnan, K.K., van der Merwe, J.E.: A flexible model for resource management in virtual private networks. In: Proc. of the ACM SIGCOMM Computer Communication Review, vol. 29, pp. 95–109 (1999)

    Google Scholar 

  17. Fingerhut, J.A., Suri, S., Turner, J.: Designing least-cost nonblocking broadband networks. J. Algorithms 24, 287–309 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  18. Goyal, N., Olver, N., Shepherd, B.: Dynamic vs oblivious routing in network design. In: 17th Annual European Symposium on Algorithms (ESA 2009) (2009)

    Google Scholar 

  19. Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: Provisioning a virtual private network: a network design problem for multicommodity flows. In: Proc. of ACMSTOC 2001, pp. 389–398 (2001)

    Google Scholar 

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

  21. Koster, A., Kutschka, M., Raack, C.: Robust network design: formulations, valid inequalities, and computations. Technical report 11-34, ZIB (2011)

  22. Magnanti, T.L., Mirchandani, P., Vachani, R.: The convex hull of two core capacitated network design problems. Math. Program. 60, 233–250 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  23. Magnanti, T.L., Mirchandani, P., Vachani, R.: Modeling and solving the two-facility capacitated network loading problem. Oper. Res. 43, 142–157 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mattia, S.: Separating tight metric inequalities by bilevel programming. Technical report 16-11, IASI-CNR (2011)

  25. Mattia, S.: Solving survivable two-layer network design problems by metric inequalities. Comput. Optim. Appl. 51(2), 809–834 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  26. Minoux, M.: Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math. 158(5), 597–603 (2010)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  28. Oriolo, G.: Domination between traffic matrices. Math. Oper. Res. 33, 91–96 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  29. Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0—Survivable Network Design Library. In: Proc. of INOC 2007 (2007)

    Google Scholar 

  30. Poss, M., Raack, C.: Affine recourse for the robust network design problem: between static and dynamic routing. Technical report 11-03, ZIB (2011)

  31. Raack, C., Koster, A., Orlowski, S., Wessäly, R.: On cut-based inequalities for capacitated network design polyhedra. Networks 57(2), 141–156 (2011)

    MathSciNet  MATH  Google Scholar 

  32. Sanità, L.: Robust network design. PhD thesis, Sapienza, Università di Roma (2008)

Download references

Author information

Authors and Affiliations

  1. IASI, Istituto di Analisi dei Sistemi ed Informatica, CNR, Consiglio Nazionale delle Ricerche, viale Manzoni 30, 00185, Rome, Italy

    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.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mattia, S. The robust network loading problem with dynamic routing. Comput Optim Appl 54, 619–643 (2013). https://doi.org/10.1007/s10589-012-9500-0

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-012-9500-0

Keywords

Search

Navigation