R. Kawatra (USA)
Architecture Design and Infrastructure, topology, networks, and mathematical formulation
The Multiperiod Minimal Spanning Tree (MMST) 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. Some of the terminal nodes are available in the network at the beginning of the planning horizon while others are added over time. We formulate this problem as an integer programming problem. We suggest a Lagrangean 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 Lagrangean based heuristic method yields verifiably good solutions to this hard problem.
Important Links:
Go Back
