A multiperiod planning model for the capacitated minimal spanning tree problem

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. (C) 2000 Elsevier Science B.V. All rights reserved.