An exact algorithm for robust network design

Christoph Buchheim, Frauke Liers, Laura Sanità

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationNetwork Optimization - 5th International Conference, INOC 2011, Proceedings
Pages7-17
Number of pages11
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event5th International Conference on Network Optimization, INOC 2011 - Hamburg, Germany
Duration: 13 Jun 201116 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6701 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Conference on Network Optimization, INOC 2011
Country/TerritoryGermany
CityHamburg
Period13/06/1116/06/11

Fingerprint

Dive into the research topics of 'An exact algorithm for robust network design'. Together they form a unique fingerprint.

Cite this