Universität zu Köln

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

Preview

PDF RND.pdf - Submitted Version Download (339kB) | Preview

Abstract

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.

Item Type:	Book Section
Creators:	Creators Email ORCID ORCID Put Code Álvarez-Miranda, Eduardo UNSPECIFIED UNSPECIFIED UNSPECIFIED Liers, Frauke UNSPECIFIED UNSPECIFIED UNSPECIFIED Lodi, Andrea UNSPECIFIED UNSPECIFIED UNSPECIFIED Parriani, Tiziano UNSPECIFIED UNSPECIFIED UNSPECIFIED Schmidt, Daniel R. UNSPECIFIED https://orcid.org/0000-0001-7381-912X UNSPECIFIED Cacchiani, Valentina UNSPECIFIED UNSPECIFIED UNSPECIFIED Dorneth, Tim UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550224
Title of Book:	Combinatorial Optimization : Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers
Series Name:	Lecture notes in computer science
Volume:	7422
Page Range:	pp. 261-272
Number of Pages:	261-272
Date:	2012
Publisher:	Springer-Verlag
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55022