• search hit 23 of 153
Back to Result List

Robust Network Design: Formulations, Valid Inequalities, and Computations

Please always quote using this URN:urn:nbn:de:0296-matheon-9959
  • 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 Bertsimas and Sim [21]. 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. We show that these inequalities define facets under certain conditions and that they completely describe a projection of the robust cutset polyhedron if the cutset consists of a single edge. 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Raack, Arie M.C.F Koster, Manuel Kutschka
URN:urn:nbn:de:0296-matheon-9959
Referee:Martin Grötschel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/01/20
Release Date:2012/01/20
Tag:cutset inequalities; robust network design
Institute:Zuse Institute Berlin (ZIB)
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B15 Network models, stochastic
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
Preprint Number:863
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.