Column generation for dimensioning resilient optical grid networks with relocation

Nowadays, the Quality of Service (QoS) in Optical Grids has become a key issue. An important QoS factor is resiliency, namely the ability to survive from certain network failures. Although several traditional network protection schemes were devised in the past, they are not optimized for Optical Grids. In an earlier work, we proposed relocation strategies providing backup paths to alternate destinations, exploiting the anycast routing principle of grids. To show the advantage of relocation (compared to traditional network protection) in terms of reduced network capacity, we formulated the network dimensioning problem as an Integer Linear Program (ILP). Yet, its solution exhibited very poor scalability and appeared not practical for reasonably large scale case studies. Therefore, we propose a novel formulation for the relocation protection scheme, using column generation (CG). This approach decomposes the original ILP into two parts, specifically a Restricted Master Problem (RMP) and a Pricing Problem (PP) which are iteratively and alternatively solved until the optimality condition is satisfied. Such a CG decomposition has a significant impact on the complexity of the model, leading to a significant improvement over previous ILPs in term of scalability and running times. We demonstrate that the CG method is highly scalable and generates nearly optimal solutions using case studies with up to 300 connections, showing it to be highly competitive with a previously proposed heuristic. We also perform some comparisons of the anycast scheme with the classical shared path protection on larger network instances.