Single-Commodity Robust Network Design with Finite and Hose Demand Sets

Cacchiani, Valentina and Jünger, Michael and Liers, Frauke and Lodi, Andrea and Schmidt, Daniel R. (2014) Single-Commodity Robust Network Design with Finite and Hose Demand Sets.
Technical Report , 32 p.
Submitted

Abstract

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 strenghtened 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.


Actions:
Download: [img] PDF - Preprinted Version
Download (334Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: UNSPECIFIED
Depositing User: Daniel R. Schmidt
Date Deposited: 03 Apr 2014 10:15
Last Modified: 15 Apr 2014 15:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/771