University of Minnesota
University Relations

Minnesota Supercomputing Institute

Log out of MyMSI

Research Abstracts Online
January 2008 - March 2009

Minnesota State University, Mankato
College of Business
Department of Management

PI: Rakesh Kawatra

A Multiperiod Hop-constrained Min-Sum Arborescence Problem

The multiperiod hop-constrained arborescence problem consists of scheduling the installation of links in a network so as to connect a set of terminal nodes N = {2,3, ......n} to a central node with minimal present value of expenditure 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; the number of links from the central node to each terminal node t is limited to a predefined value h; and some terminal nodes are activated at the beginning of the planning horizon while the remaining terminal nodes are activated over time. This researcher has formulated this as an integer programming problem. He is using a Lagrangian-based heuristic to solve the integer programming formulation of the network topology problem.