Lagrangian decomposition, metaheuristics, and hybrid approaches for the design of the last mile in fiber optic networks

Markus Leitner*, Günther R. Raidl

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationHybrid Metaheuristics - 5th International Workshop, HM 2008, Proceedings
PublisherSpringer - Verlag
Pages158-174
Number of pages17
ISBN (Print)3540884386, 9783540884385
DOIs
Publication statusPublished - 1 Jan 2008
Externally publishedYes
Event5th International Workshop on Hybrid Metaheuristics, HM 2008 - Malaga, Spain
Duration: 8 Oct 20089 Oct 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5296 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Workshop on Hybrid Metaheuristics, HM 2008
CountrySpain
CityMalaga
Period8/10/089/10/08

Keywords

  • Greedy randomized adaptive search procedure
  • Lagrangian relaxation
  • Network design
  • Redundancy
  • Steiner tree problem
  • Survivable network design
  • Variable neighborhood search

Fingerprint Dive into the research topics of 'Lagrangian decomposition, metaheuristics, and hybrid approaches for the design of the last mile in fiber optic networks'. Together they form a unique fingerprint.

Cite this