Premium
Reload cost trees and network design
Author(s) -
Gamvros Ioannis,
Gouveia Luis,
Raghavan S.
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20443
Subject(s) - computer science , network planning and design , spanning tree , graph , tree (set theory) , mathematical optimization , theoretical computer science , computer network , mathematics , combinatorics , mathematical analysis
In this article, we consider the notion of “reload costs” in network design. Reload costs occur naturally in many different settings including telecommunication networks using diverse technologies. However, reload costs have not been studied extensively in the literature. Given that reload costs occur naturally in many settings, we are motivated by the desire to develop “good” models for network design problems involving reload costs. In this article, and as a first step in this direction, we propose and discuss the reload cost spanning tree problem (RCSTP). We show that the RCSTP is NP‐complete. We discuss several ways of modeling network design problems with reload costs. These involve models that expand the original graph significantly—to a directed line graph and a colored graph—to model reload costs. We show that the different modeling approaches lead to models with the same linear programming bound. We then discuss several variations of reload cost spanning tree and network design problems, and discuss both their complexity and models for these variations. To assess the effectiveness of the proposed models to solve RCSTP instances, we present results taken from instances with up to 50 nodes, 300 edges, and nine technologies for several variations of the problem. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011