Lagrangean price directive ring generation for network design
2003 (English)Report (Other academic)
This paper addresses the problem of designing a telecommunication network with certain survivability requirements, namely that the network should be made up between connected rigs. This way single link failures do not kill the connection between any two nodes. One can make the network two-node-connected by including two specific nodes in all rings. This gives rise to a network design optimization problem with fixed costs on rings. In this paper we describe a solution approach for such problems, based on generation of rings. The approach is in principle a column generation technique, where the dual prices used for pricing out columns are obtained with the help of Lagrange duality, instead of the usual LP-duality. Computational tests are reported.
Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2003. , 19 p.
LiTH-MAT-R, ISSN 0348-2960 ; 17
network design, rings, column generation, Lagrange multipliers
IdentifiersURN: urn:nbn:se:liu:diva-22370Local ID: 1578OAI: oai:DiVA.org:liu-22370DiVA: diva2:242683