Optimization Online


A new model and a computational study for Demand-wise Shared Protection

Claus G. Gruber (claus.gruber***at***tum.de)
Arie M.C.A. Koster (koster***at***zib.de)
Sebastian Orlowski (orlowski***at***zib.de)
Roland Wessaely (wessaely***at***zib.de)
Adrian Zymolka (zymolka***at***zib.de)

Abstract: This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15% percent worse than shared path protection.

Keywords: demand-wise shared protection, resilience, network design, integer linear programming

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Network Optimization

Citation: ZIB-Report 05-55, Zuse Institute Berlin, Germany http://www.zib.de/

Download: [Compressed Postscript][PDF]

Entry Submitted: 12/22/2005
Entry Accepted: 01/02/2006
Entry Last Modified: 01/22/2006

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 Programming Society