by Michael Poss, CR CNRS researcher HDS
We study the problem of designing a telecommunications network when the demand is uncertain and belong to a known polytope. The problem has a natural two-stage structure. First, we must decide how much capacity to install on the links of the networks. Then, for each possible demand realization, we must decide of a routing in the network for each point-to-point commodity. This two-stage structure leads to NP-hard optimization problems in general. The absence of restriction on the routing is known as dynamic routing.
We present in this talk a simplified approach to the problem. We suppose that the routing is defined by affine functions of the uncertainties which leads to optimization problems that are solvable in polynomial time. 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 solutions. We investigate properties of 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 realistic telecommunications networks. 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.