Rakesh Kawatra, Principal Investigator

Multiperiod Minimal Spanning Tree Problem—Formulation and Solution Methods

The Multiperiod Minimal Spanning Tree (MMST) problem consists of scheduling the installation of links in a network so as to connect a set of nodes to a central node with minimal present value of expenditures. Some of the nodes in the network are active at the beginning of the planning horizon while others are activated over time. The problem was formulated as an integer programming problem. This research suggests a Lagrangian-based heuristic to solve the integer programming formulation of the network 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.