A new flow formulation for FIPP p-cycle protection subject to multiple link failures

We propose a new generic flow formulation for Failure-Independent Path-Protecting (FIPP) p-cycles subject to multiple failures. While our new model resembles the decomposition model formulation proposed by Orlowski and Pioro (2011) in the case of classical shared path protection, its originality lies in its adaptation to FIPP p-cycles. When adapted to that last pre-configured pre-cross connected protection scheme, the bandwidth sharing constraints must be handled in a different way in order to take care of the sharing along the FIPP p-cycles. It follows that, instead of a polynomial-time solvable pricing problem as in the model of Orlowski and Pioro (2011), we end up with a more complex pricing problem, which is no more polynomially solvable. We therefore focused on speeding up the iterative solution process of the pricing problems using a hierarchical decomposition of the original pricing problem. Performance evaluation is made in the case of FIPP p-cycles subject to dual failures. The proposed model remains fairly scalable for increasing percentages of dual failures, and requires much less bandwidth than p-cycle protection schemes (ratio varies from 2 to 4). In the particular case of single link failures, it compares favorably to the previously proposed column generation ILP model of Rocha, Jaumard and Stidsen (2011).