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 arbi-trary recourse. Following Ouorou and Vial, we apply them to robust network design with polyhedral demand uncertainty, introducing the notion of affine routing. We compare the new affine routing scheme 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 while still being tractable and providing cheaper solu-tions. We investigate properties of the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set lead-ing 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 computa-tional 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 net-work 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 ar