A multiperiod degree constrained minimal spanning tree problem

The multiperiod degree constrained minimal spanning tree problem consists of scheduling the installation of links in a network so as to connect a set of terminal nodes to a central node with minimal present value of expenditures. The network design is subject to degree constraint, which limits the number of links incident on each terminal node to a prespecified number due to the number of ports available on it. Some of the terminal nodes in the network are active at the beginning of the planning horizon while others are activated over time. We formulate this problem as an integer programming problem. We suggest a Lagrangian-based heuristic to solve the integer programming formulation of the network topology problem. Lower bounds found as a byproduct of the solution procedure are used to estimate the quality of the solution given by the heuristic. Experimental results over a wide range of problem structures show that the Lagrangian-based heuristic method yields verifiably good solutions to this hard problem.