• search hit 8 of 24
Back to Result List

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

Submission Status:in press
  • 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.
Metadaten
Author:Valentina Cacchiani, Michael Jünger, Frauke Liers, Andrea Lodi, Daniel Schmidt
DOI:https://doi.org/10.1007/s10107-016-0991-9
Parent Title (English):Mathematical Programming
Document Type:Article
Language:English
Date of Publication (online):2016/03/25
Date of first Publication:2016/05/01
Release Date:2016/09/20
Tag:Branch-and-cut; Cut-set inequalities; Polyhedral demand uncertainty; Robust network design; Separation under uncertainty
Volume:157
Issue:1
First Page:297
Last Page:342
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
University of Bologna
Universität zu Köln
École Polytechnique de Montréal
Subprojects:B06