SingleCommodity 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)
SingleCommodity Robust Network Design with Finite and Hose Demand Sets.
Technical Report
, 32 p.
This is the latest version of this item.
Abstract
We study a singlecommodity 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 singlecommodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branchand cut algorithm to derive optimal solutions to sRND, built on a capacitybased integer linear programming formulation. It is strenghtened with valid inequalities derived as {0,1/2 }ChvátalGomory 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.
Download: 
PDF
 Preprinted Version
Download (342kB)  Preview 

Editorial actions:  View Item (Login required) 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Daniel R. Schmidt 
Date Deposited:  06 Nov 2019 13:57 
Last Modified:  06 Nov 2019 13:57 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/944 
Available Versions of this Item

SingleCommodity Robust Network Design with Finite and Hose Demand Sets. (deposited 03 Apr 2014 10:15)
 SingleCommodity Robust Network Design with Finite and Hose Demand Sets. (deposited 06 Nov 2019 13:57) [Currently Displayed]