The Multiperiod Capacitated Minimal Spanning Tree (MCMST) Problem consists of scheduling the installation of links in a network so as to connect a set of terminal nodes S=[2,3, ..., N] to a central node (node 1) with minimal present value of expenditures, where link capacities limit the number of terminal nodes sharing a link. Some of the terminal nodes are active at the beginning of the planning horizon while others are activated over time. We formulate this problem as an integer programming problem. A branch exchange heuristic procedure for solving the problem is presented. We also present a Lagrangian relaxation method to find a lower bound for the optimal objective function value. This lower bound may be used to estimate the quality of the solution given by the branch exchange heuristic. Experimental results over a wide range of problem structures show that the branch exchange heuristic method yields verifiably good solutions to this problem.
