Optimization Online


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

Valentina Cacchiani(valentina.cacchiani***at***unibo.it)
Michael Jünger(mjuenger***at***informatik.uni-koeln.de)
Frauke Liers(frauke.liers***at***math.uni-erlangen.de)
Andrea Lodi(andrea.lodi***at***unibo.it)
Daniel Schmidt(schmidt***at***informatik.uni-koeln.de)

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

Keywords: Robust Optimization, Network Design, Branch-and-Cut, Polyhedral Uncertainty

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Robust Optimization


Download: [PDF]

Entry Submitted: 01/26/2015
Entry Accepted: 02/01/2015
Entry Last Modified: 01/26/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society