Publication Date:
2020-08-05
Description:
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.
Language:
English
Type:
reportzib
,
doc-type:preprint
Format:
application/pdf
