Nothing Special   »   [go: up one dir, main page]

Skip to main content

Affine Recourse for the Robust Network Design Problem: Between Static and Dynamic Routing

  • Conference paper
Network Optimization (INOC 2011)

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 6701))

Included in the following conference series:

Abstract

Affinely-Adjustable Robust Counterparts are used to provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even strongly) dominated demand vectors are not necessarily supported by affine solutions.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Altin, A., Amaldi, E., Belotti, P., Pinar, Ç.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1), 100–115 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ben-Ameur, W., Kerivin, H.: New economical virtual private networks. Communications of the ACM 46(6), 69–73 (2003)

    Article  Google Scholar 

  3. Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Prog. 99(2), 351–376 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bertsimas, D., Goyal, V.: On the power and limitations of affine policies in two-stage adaptive optimization. Math. Prog., 1–41 (2011) (in press)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  6. Oriolo, G.: Domination between traffic matrices. Mathematics of Operations Research 33(1), 91–96 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0–Survivable Network Design Library. Networks 55(3), 276–286 (2010)

    Google Scholar 

  8. Ouorou, A., Vial, J.P.: A model for robust capacity planning for telecommunications networks under demand uncertainty. In: 6th Intl. Workshop on Design and Reliable Communication Networks, pp. 1–4 (2007)

    Google Scholar 

  9. Scutellà, M.G.: On improving optimal oblivious routing. Operations Research Letters 37(3), 197–200 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Poss, M., Raack, C. (2011). Affine Recourse for the Robust Network Design Problem: Between Static and Dynamic Routing. In: Pahl, J., Reiners, T., Voß, S. (eds) Network Optimization. INOC 2011. Lecture Notes in Computer Science, vol 6701. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21527-8_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-21527-8_19

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-21526-1

  • Online ISBN: 978-3-642-21527-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics