A ring network design problem solved by a ring generation and allocation approach
2003 (English)Report (Other academic)
The development of optical fibers in telecommunications has lead large changes in the field. When design a telecommunication network, capacity nowadays is cheap, and the minimal cost design tends to be a tree. Since such a design is very vulnerable for link or node failures, one often wish to include some kind of survivability requirement, for example that the network should be two-edge-connected or two-node-connected. Another form of design model is to prescribe that the network should be composed of connected rings of links. The network design problem is then to choose links from a give network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. Each possible ring is associated with a certain fixed cost, and all links in a certain ring are given the same capacity. Traffic between rings may pass through other rings, which is an important element of the problem. Finally, reserve capacity allocation according to certain principles is included. We describe the problem, modeled as a linear integer programming problem, and discuss different formulations and different solution methods. As the problem is quite difficult, we focus on heuristic solution methods, including elements of column generation and Lagrangean relaxation.
Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2003. , 37 p.
LiTH-MAT-R, ISSN 0348-2960 ; 20
IdentifiersURN: urn:nbn:se:liu:diva-22366Local ID: 1574OAI: oai:DiVA.org:liu-22366DiVA: diva2:242679