Article ID: | iaor20106832 |
Volume: | 48 |
Issue: | 2 |
Start Page Number: | 335 |
End Page Number: | 345 |
Publication Date: | Oct 2010 |
Journal: | Journal of Global Optimization |
Authors: | Liang Zhe, Art Chaovalitwongse Wanpracha |
This paper proposes three classes of alternative mathematical programming models (i.e., edge-based, path-based, and tree-based) for redundant multicast routing problem with shared risk link group (SRLG)-diverse constraints (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 from 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 services. We investigated and compared the theoretical bounds of the linear programming (LP) relaxation for all models. We also summarized a hierarchy relationship of the tightness of LP bounds for the proposed models.