Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs

The degree-constrained minimal spanning tree (DCMST) problem with unreliable links and node outage costs consists of finding links in a network to connect a set of terminal nodes to a central node while minimizing the expected annual expenditure. The number of ports available on each terminal node limits the number of incident links (the degree constraint). Each terminal node in the network has an associated node outage cost, which is the economic cost incurred by the network user whenever that node is disabled due to failure of a link. We formulate this problem as an integer-programming problem and present a Lagrangian relaxation method which, for each choice of Lagrangian multipliers, provides a lower bound for the optimal objective function value. A subgradient optimization method is used to search for multipliers which yield good lower bounds. A branch exchange heuristic procedure makes modifications to each infeasible solution of the Lagrangian relaxation in order to find good feasible solutions. The quality of these heuristic solutions is estimated using the best obtained lower bounds. Experimental results over a wide range of problem structures show that the branch exchange heuristic method yields verifiably good solutions to this problem.