Ring Network Design by Lagrangean Based Column Generation |
| |
Authors: | Henningsson M Holmberg K Rönnqvist M Värbrand P |
| |
Affiliation: | (1) Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden |
| |
Abstract: | 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. |
| |
Keywords: | network design rings column generation Lagrangean relaxation heuristic |
本文献已被 SpringerLink 等数据库收录! |
|