Hop Constrained Network Design Problem with Partial Survivability

This paper studies the hop constrained network design problem with partial survivability, namely, given an undirected network, a set of point-to-point demands (commodities), and transmission link costs, identify two node disjoint paths for each demand (commodity) to minimize the total costs subject to the constraints that each demand is routed and traverses at most a specified number of links (or hops) on both the paths.A mathematical programming formulation of the problem is presented and an efficient solution procedure based on the linear programming relaxation is developed. Extensive computational results across a number of networks are reported. These results indicate that the solution procedure is effective for a wide range of problem sizes.