Abstract
The Multiperiod Capacitated Minimal Spanning Tree With Node Outage Costs (MCMSTWOC) Design problem consists of scheduling the installation of links in a communication 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 costs. The cost of the network is the sum of link layout cost and node outage costs. The link capacities limit the number of terminal nodes sharing a link. Node outage cost associated with each terminal node is the economic cost incurred by the network user whenever the terminal node is disabled due to failure of a link. In the network some of the terminal nodes are active at the beginning of the planning horizon while others are activated over time. The problem is formulated as an integer-programming problem. A Lagrangian relaxation method is used to find a lower bound for the optimal objective function value. Subgradient optimization method is used to find good lower bounds. This lower bound can be used to estimate the quality of the solution given by a heuristic.
Recommended Citation
Kawatra, Rakesh, "Lower Bounds for the Multiperiod Capacitated Minimal Spanning Tree with Node Outage Cost Design Problem" (2000). AMCIS 2000 Proceedings. 325.
https://aisel.aisnet.org/amcis2000/325