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

Export as: 
[error in script] 
Editorial actions: 
View Item (Login required) 
Item Type: 
Paper
(Technical Report)

Citations: 
[error in script]
[error in script]

Subjects: 
90XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B10 Network models, deterministic
90XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B18 Communication networks
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C11 Mixed integer programming
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks
90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branchandbound, branchandcut

Additional Information: 
Also appeared as technical report OR1411 at the University of Bologna, Italy. 
Subjects: 
90XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B10 Network models, deterministic 90XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B18 Communication networks 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C11 Mixed integer programming 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C35 Programming involving graphs or networks 90XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C57 Polyhedral combinatorics, branchandbound, branchandcut 
Divisions: 
Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Depositing User: 
Daniel R. Schmidt

Date Deposited: 
03 Apr 2014 10:15 
Last Modified: 
15 Apr 2014 15:46 