Ring network design by Lagrangean based column generation
2002 (English)In: Telecommunications Systems, ISSN 1018-4864, E-ISSN 1572-9451, Vol. 21, no 2-4, 301-318 p.Article in journal (Refereed) Published
We discuss the problem of designing a telecommunication network with the survivability requirement that the network should be composed of connected rings of links. The network design problem is then to choose links from a given network, and compose them into a number of rings. Furthermore, the rings should be connected at certain transit nodes. The traffic between rings may pass through other rings. Each ring is associated with a certain fixed cost depending on the length of the ring. We describe the problem, modeled as a linear integer programming problem, and a heuristic solution method, based on column generation and Lagrangean relaxation.
Place, publisher, year, edition, pages
2002. Vol. 21, no 2-4, 301-318 p.
network design, rings, column generation, Lagrangean relaxation, heuristic
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-48707DOI: 10.1023/A:1020954800383OAI: oai:DiVA.org:liu-48707DiVA: diva2:269603