Models and Algorithms for Robust Network Design with Several Traffic Scenarios

Álvarez-Miranda, Eduardo and Cacchiani, Valentina and Dorneth, Tim and Jünger, Michael and Liers, Frauke and Lodi, Andrea and Parriani, Tiziano and Schmidt, Daniel R. (2012) Models and Algorithms for Robust Network Design with Several Traffic Scenarios.
Published In: Combinatorial Optimization : Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers, Lecture notes in computer science. 7422 Springer-Verlag 2012, pp. 261-272.


We consider a robust network design problem in which optimum integral capacities need to be installed on the edges of a network such that the supplies and demands in each of the explicitly known traffic scenarios are 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. In this work, we introduce an IP formulation that only uses capacity variables and exponentially many constraints that can be separated in polynomial time. We argue that the latter formulation has advantageous features when used within branch and cut and evaluate preliminary computational results for the bounds in the root node. We introduce a class of instances that is difficult for IP-based solution approaches. We design and implement a heuristic solution approach based on the definition and exploration of large neighborhoods of carefully selected size. The performance of the heuristic is evaluated on the difficult class of instances. The results are encouraging, with a good understanding of the trade-off between solution quality and neighborhood size.

Download: [img] PDF - Preprinted Version
Download (339kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Daniel R. Schmidt
Date Deposited: 09 Dec 2011 11:08
Last Modified: 08 Nov 2012 14:14