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

Please always quote using this URN: urn:nbn:de:0296-matheon-7753

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.

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Michael Poss, Christian Raack
URN:urn:nbn:de:0296-matheon-7753
Referee:Martin Grötschel
Language:English
Date of first Publication:16.12.2011
Tag:affine adjustable robust counterparts; affine routing; demand polytope; network design; recourse; robust optimization
Institute:Zuse Institute Berlin (ZIB)
Project:B3 Integrated Planning of Multi-layer Telecommunication Networks
MSC-Classification:90B15 Network models, stochastic
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks [See also 90C27]
90C90 Applications of mathematical programming
Preprint Number:Matheon Preprint #832