Paper Info
Title
Models and algorithms for robust network design with several traffic scenarios
Abstract
We consider a robust network design problem: optimum integral capacities need to be installed in a network such that supplies and demands in each of the explicitly known traffic scenarios can be satisfied by a single-commodity flow. In Buchheim et al. (LNCS 6701, 7---17 (2011)), an integer-programming (IP) formulation of polynomial size was given that uses both flow and capacity variables. We introduce an IP formulation that only uses capacity variables and exponentially many, but polynomial time separable constraints. We discuss the advantages of the latter formulation for branch-and-cut implemenations and evaluate preliminary computational results for the root bounds. We define a class of instances that is difficult for IP-based approaches. Finally, we design and implement a heuristic solution approach based on the exploration of large neighborhoods of carefully selected size and evaluate it on the difficult instances. The results are encouraging, with a good understanding of the trade-off between solution quality and neighborhood size.
Year
DOI
Venue
2012
10.1007/978-3-642-32147-4_24
ISCO
Keywords
Field
DocType
ip formulation,optimum integral capacity,polynomial time separable constraint,robust network design problem,capacity variable,heuristic solution approach,difficult instance,polynomial size,traffic scenario,latter formulation,neighborhood size
Mathematical optimization,Heuristic,Polynomial,Network planning and design,Separable space,Time complexity,Mathematics,Large neighborhood search,Exponential growth
Conference
Citations 
PageRank 
References 
2
0.37
19
Authors
8
Name
Order
Citations
PageRank
Eduardo Álvarez-Miranda15411.25
Valentina Cacchiani229224.01
Tim Dorneth320.37
Michael Jünger41194393.00
Frauke Liers5608.89
Andrea Lodi62198152.51
Tiziano Parriani751.43
Daniel R. Schmidt8132.28