Optimization Online


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

Michael Poss (mposs***at***ulb.ac.be)
Christian Raack (raack***at***zib.de)

Abstract: 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.

Keywords: robust optimization, network design, recourse, affine adjustable robust counterparts, affine routing, demand polytope

Category 1: Robust Optimization

Category 2: Network Optimization

Category 3: Combinatorial Optimization

Citation: ZIB-Report 11-03, February 2011, Zuse Institute Berlin Takustr. 7, 14195 Berlin, Germany

Download: [PDF]

Entry Submitted: 02/08/2011
Entry Accepted: 02/08/2011
Entry Last Modified: 02/08/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society