Single-commodity robust network design with finite and Hose demand sets

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autorinnen und Autoren: Cacchiani V, Jünger M, Liers F, Lodi A, Schmidt DR
Zeitschrift: Mathematical Programming
Jahr der Veröffentlichung: 2016
Band: 157
Heftnummer: 1
Seitenbereich: 297-342
ISSN: 1436-4646


We study a single-commodity robust network design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strengthened with valid inequalities derived as { 0 , 1 2 } -Chvátal–Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver.

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
University of Bologna / Università di Bologna


Cacchiani, V., Jünger, M., Liers, F., Lodi, A., & Schmidt, D.R. (2016). Single-commodity robust network design with finite and Hose demand sets. Mathematical Programming, 157(1), 297-342.

Cacchiani, Valentina, et al. "Single-commodity robust network design with finite and Hose demand sets." Mathematical Programming 157.1 (2016): 297-342.


Zuletzt aktualisiert 2018-04-10 um 21:50