P-cycle and FIPPp-cycle networks design

LOISEAU, IRENE; PECORARI, AGUSTÍN

Quebec

Congreso; IFORS 2017 (21 Conference of the International Federation of Operational Research Societies); 2017

IFORS (http://www.ifors.org)

A telecommunication network is said to be survivable if it is still able to provide communication between sites it connects after certain component fails, by redirecting traffic to parts of the network where spare capacity has been installed. We want to design minimum cost survivable networks (SCA, Spare Capacity Allocation Problem). Mesh restoration schemes were used in the 1970s and early 1980s. Self-healing ring based topologies were introduced in the late 80s. In the late 90s the p-cycle architecture concept was proposed. This approach is reported to simultaneously provide the switching speed and simplicity of rings with the much greater efficiency for reconfiguration of a mesh network. A single unit capacity p-cycle is a cycle having one spare channel on each span it crosses. It provides one protection path for a failed span on the cycle and it also protects spans that have both end nodes on the cycle but are not on the cycle. This concept was extended to the FIPP (failure independent path protection) architectures where p-cycles are able to protect paths. We proposed models and algorithms for the SCA with p-cycles and FIPP p-cycles. We will focus here on the FIPP problem. We present a new mixed integer programming model and branch and cut method, a constraint programming formulation, a GRASP algorithm with exact local search and a branch-and-price algorithm. We tested them on real networks and artificial ones. The branch-and-cut algorithm showed to be the most efficient.