A hop constrained min-sum arborescence with outage costs

The hop constrained min-sum arborescence with outage costs problem consists of selecting links in a network so as to connect a set of terminal nodes N={2,3, ...n} to a central node with minimal total link cost such that (a) each terminal node j has exactly one entering link; (b) for each terminal node j, a unique path from the central node to j exists; (c) for each terminal node j the number of links between the central node and j is limited to a predefined number h_j, and (d) each terminal node has an associated outage cost, which is the economic cost incurred by the network user whenever that node is disabled due to failure of a link. We suggest a Lagrangian based heuristic to solve the integer programming formulation of this network problem.