TY - GEN
T1 - Lagrangian decomposition, metaheuristics, and hybrid approaches for the design of the last mile in fiber optic networks
AU - Leitner, Markus
AU - Raidl, Günther R.
PY - 2008/1/1
Y1 - 2008/1/1
N2 - We consider a generalization of the (Price Collecting) Steiner Tree Problem on a graph with special redundancy requirements for customer nodes. The problem occurs in the design of the last mile of real-world communication networks. We formulate it as an abstract integer linear program and apply Lagrangian Decomposition to obtain relatively tight lower bounds as well as feasible solutions. Furthermore, a Variable Neighborhood Search and a GRASP approach are described, utilizing a new construction heuristic and special neighborhoods. In particular, hybrids of these methods are also studied and turn out to often perform superior. By comparison to previously published exact methods we show that our approaches are applicable to larger problem instances, while providing high quality solutions together with good lower bounds.
AB - We consider a generalization of the (Price Collecting) Steiner Tree Problem on a graph with special redundancy requirements for customer nodes. The problem occurs in the design of the last mile of real-world communication networks. We formulate it as an abstract integer linear program and apply Lagrangian Decomposition to obtain relatively tight lower bounds as well as feasible solutions. Furthermore, a Variable Neighborhood Search and a GRASP approach are described, utilizing a new construction heuristic and special neighborhoods. In particular, hybrids of these methods are also studied and turn out to often perform superior. By comparison to previously published exact methods we show that our approaches are applicable to larger problem instances, while providing high quality solutions together with good lower bounds.
KW - Greedy randomized adaptive search procedure
KW - Lagrangian relaxation
KW - Network design
KW - Redundancy
KW - Steiner tree problem
KW - Survivable network design
KW - Variable neighborhood search
UR - https://www.scopus.com/pages/publications/57049164290
UR - https://www.scopus.com/pages/publications/57049164290#tab=citedBy
U2 - 10.1007/978-3-540-88439-2_12
DO - 10.1007/978-3-540-88439-2_12
M3 - Conference contribution
AN - SCOPUS:57049164290
SN - 3540884386
SN - 9783540884385
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 158
EP - 174
BT - Hybrid Metaheuristics - 5th International Workshop, HM 2008, Proceedings
PB - Springer - Verlag
T2 - 5th International Workshop on Hybrid Metaheuristics, HM 2008
Y2 - 8 October 2008 through 9 October 2008
ER -