Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Affine recourse for the robust network design problem: Between static and dynamic routing

  • Affinely-Adjustable Robust Counterparts 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. All three schemes are embedded into the general framework of two-stage network design with recourse. 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 totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Michael Poss, Christian Raack
Document Type:Article
Parent Title (English):Networks - Special Issue: INOC 2011 Conference, June 13–16, 2011, Hamburg, Germany
Volume:61
Issue:2
First Page:180
Last Page:198
Year of first publication:2013
Preprint:urn:nbn:de:0297-zib-12122
DOI:https://doi.org/10.1002/net.21482
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.