Chance Constrained Network Design

When designing or upgrading a communication network, operators are faced with a major issue, as uncertainty on communication demands makes it difficult to correctly provision the network capacity. When a probability on traffic matrices is given, finding the cheapest capacity allocation that guarantees, within a prescribed level of confidence, that each arc can support the traffic demands peaks turns out to be, in general, a difficult non convex optimization problem belonging to the class of chance constrained problems. Drawing from some very recent results in the literature we highlight the relationships between chance constrained network design problems and robust network optimization. We then compare several different ways to build uncertainty sets upon deviation measures, comprised the recently proposed backward and forward deviation measures that capture possible asymmetries of the traffic demands distribution. We report results of a computational study aimed at comparing the performance of different models when built upon the same set of historical traffic matrices.