Models and algorithms for robust network design with several traffic scenarios

Beitrag in einem Sammelwerk
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Álvarez-Miranda E, Cacchiani V, Dorneth T, Jünger M, Liers F, Lodi A, Parriani T, Schmidt DR
Herausgeber: A. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos
Titel Sammelwerk: Combinatorial Optimization
Verlag: Springer
Verlagsort: Berlin, Heidelberg
Jahr der Veröffentlichung: 2012
Titel der Reihe: Lecture Notes in Computer Science
Band: 7422
Seitenbereich: 261-272
ISBN: 9783642321467


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. © 2012 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

Universität Köln
Universität zu Köln
University of Bologna / Università di Bologna


Zitierweisen

APA:
Álvarez-Miranda, E., Cacchiani, V., Dorneth, T., Jünger, M., Liers, F., Lodi, A.,... Schmidt, D.R. (2012). Models and algorithms for robust network design with several traffic scenarios. In A. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos (Eds.), Combinatorial Optimization. (pp. 261-272). Berlin, Heidelberg: Springer.

MLA:
Álvarez-Miranda, Eduardo, et al. "Models and algorithms for robust network design with several traffic scenarios." Combinatorial Optimization. Ed. A. Ridha Mahjoub, Vangelis Markakis, Ioannis Milis, Vangelis Th. Paschos, Berlin, Heidelberg: Springer, 2012. 261-272.

BibTeX: 

Zuletzt aktualisiert 2018-19-10 um 14:53