A tree-based model for redundant multicast routing problem with shared risk link group diverse constraints

We propose a tree-based mathematical programming model for redundant multicast routing problem with Shared risk link group (SRLG)-diverse constraint (RMR-SRLGD). The goal of RMR-SRLGD problem is to find two redundant multicast trees, each from one of the two sources to every destination, at a minimum cost while ensuring the paths between the two sources to a destination do not share any common risks. Such risk could cause the failures of multiple links simultaneously. Therefore, the RMR-SRLGD problem ensures the availability and reliability of multicast service. We show that the linear programming relaxation of the tree-based model can be solved efficiently by column generation. A branch-and-price exact solution algorithm is also developed for RMR-SRLGD. Our computational results show that tree-model is capable of solving the real world problems in reasonable computational time.