Rakesh Kawatra, Principal Investigator

Multiperiod Minimal Spanning Tree Problem: Formulation and Solution Methods

The Multiperiod Minimal Spanning Tree 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 integerprogramming problem. This project uses 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 results.

A new research project uses the Lagrangian based heuristic to solve the problem of the hop constrained min-sum arborescence with outage costs. This problem consists of selecting links in a network so as to connect a set of terminal nodes N = {2, 3,.......n} to a central node with minimal total link cost such that:

• Each terminal node j has exactly one entering link.
• For each terminal node j, a unique path from the central node to j exists.
• For each terminal node j the number of links between the central node and j is limited to a predefined number hj.
• Each terminal node has an associated outage cost, which is the economic cost incurred by the network user whenever that node is disabled due to failure of a link.

The size of this problem and the computing speed required to solve it make the use of the supercomputers necessary.