Robust network design: Formulations, valid inequalities, and computations

Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this article we consider telecommunication network design under traffic uncertainty, adapting the robust optimization appr...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2013-03, Vol.61 (2), p.128-149
Main Authors: Koster, Arie M.C.A., Kutschka, Manuel, Raack, Christian
Format: Article
Language:English
Subjects:
Applied sciences
Computation
Exact sciences and technology
Experimental design
Flows in networks. Combinatorial problems
Inequalities
Mathematical analysis
Mathematical models
Mathematics
network design
Networks
Operational research and scientific management
Operational research. Management science
Optimization
polyhedral combinatorics
Probability and statistics
Reliability theory. Replacement problems
robust optimization
Sciences and techniques of general use
Statistics
Traffic engineering
Traffic flow
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this article we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim [Oper Res 52 (2004), 35–53]. We present two 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 achieved 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. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013
ISSN:0028-3045
1097-0037
DOI:10.1002/net.21497