A Lagrangian based heuristic for the design of multipoint linkages in a communication network with unreliable links and node outage costs

This paper studies the capacitated minimal spanning tree with unreliable links and node outage costs problem. Tree topologies appear in the design of centralized communication networks. In these topologies the number of nodes in a subtree rooted at the central node is limited to a predefined number due to polling, loading, and response time restrictions. The links in a communication network are prone to failure. Whenever a link in these networks fails all the terminal nodes connected to the central node through that link are unable to communicate till the faulty link is repaired. In some networks such failures can have adverse economic effect on the network user. The economic effect on the network user due to inability of a terminal to communicate with the central node due to link failure is called node outage cost. The sum of expected yearly node outage costs for a network depends on the topology of the network. In this paper we suggest a Lagrangean based heuristic to solve the integer programming formulation of the network topology problem. The objective of the problem is to minimize the sum of link costs and node outage costs. Our computational results on a set of test data with up to 80 nodes show that compared to the previously developed greedy heuristic, our method gives solutions that are better by up to 6 percent. The gaps between our heuristic solutions and the lower bounds found as a byproduct of the solution precedure are in the 2–17 percent range.