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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Altin, A., Amaldi, E., Belotti, P., Pinar, Ç.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1), 100–115 (2007)
Ben-Ameur, W., Kerivin, H.: New economical virtual private networks. Communications of the ACM 46(6), 69–73 (2003)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Prog. 99(2), 351–376 (2004)
Bertsimas, D., Goyal, V.: On the power and limitations of affine policies in two-stage adaptive optimization. Math. Prog., 1–41 (2011) (in press)
Chekuri, C., Shepherd, F.B., Oriolo, G., Scutellà, M.G.: Hardness of robust network design. Networks 50(1), 50–54 (2007)
Oriolo, G.: Domination between traffic matrices. Mathematics of Operations Research 33(1), 91–96 (2008)
Orlowski, S., Pióro, M., Tomaszewski, A., Wessäly, R.: SNDlib 1.0–Survivable Network Design Library. Networks 55(3), 276–286 (2010)
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)
Scutellà, M.G.: On improving optimal oblivious routing. Operations Research Letters 37(3), 197–200 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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)