Towards robust network design using integer linear programming techniques

Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of [11]. We present three different mathematical formulations for this problem, provide valid inequalities, study the computational implications, and evaluate the realized robustness. To enhance the performance of the mixed-integer programming solver we derive robust cutset inequalities generalizing their deterministic counterparts. Instead of a single cutset inequality for every network cut, we derive multiple valid inequalities by exploiting the extra variables available in the robust formulations. For realistic networks and live traffic measurements we compare the formulations and report on the speed up by the valid inequalities. We study the "price of robustness" and evaluate the approach by analyzing the real network load. The results show that the robust optimization approach has the potential to support network planners better than present methods.