An exact algorithm for robust network design

Beitrag in einem Sammelwerk

Details zur Publikation

Autorinnen und Autoren: Buchheim C, Liers F, Sanità L
Herausgeber: Julia Pahl, Torsten Reiners, Stefan Voß
Titel Sammelwerk: Network Optimization
Verlag: Springer
Verlagsort: Berlin Heidelberg
Jahr der Veröffentlichung: 2011
Titel der Reihe: Lecture Notes in Computer Science
Band: 6701
Seitenbereich: 7-17
ISBN: 9783642215261


Modern life heavily relies on communication networks that operate efficiently. A crucial issue for the design of communication networks is robustness with respect to traffic fluctuations, since they often lead to congestion and traffic bottlenecks. In this paper, we address an NP-hard single commodity robust network design problem, where the traffic demands change over time. For k different times of the day, we are given for each node the amount of single-commodity flow it wants to send or to receive. The task is to determine the minimum-cost edge capacities such that the flow can be routed integrally through the net at all times. We present an exact branch-and-cut algorithm, based on a decomposition into biconnected network components, a clever primal heuristic for generating feasible solutions from the linear-programming relaxation, and a general cutting-plane separation routine that is based on projection and lifting. By presenting extensive experimental results on realistic instances from the literature, we show that a suitable combination of these algorithmic components can solve most of these instances to optimality. Furthermore, cutting-plane separation considerably improves the algorithmic performance. © 2011 Springer-Verlag.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)

Einrichtungen weiterer Autorinnen und Autoren

École Polytechnique Fédérale de Lausanne (EPFL)
Universität zu Köln


Buchheim, C., Liers, F., & Sanità, L. (2011). An exact algorithm for robust network design. In Julia Pahl, Torsten Reiners, Stefan Voß (Eds.), Network Optimization. (pp. 7-17). Berlin Heidelberg: Springer.

Buchheim, Christoph, Frauke Liers, and Laura Sanità. "An exact algorithm for robust network design." Network Optimization. Ed. Julia Pahl, Torsten Reiners, Stefan Voß, Berlin Heidelberg: Springer, 2011. 7-17.


Zuletzt aktualisiert 2018-22-10 um 21:53