Hop constrained Steiner trees with multiple root nodes

Luis Gouveia, Markus Leitner*, Ivana Ljubić

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches.

Original languageEnglish
Pages (from-to)100-112
Number of pages13
JournalEuropean Journal of Operational Research
Volume236
Issue number1
DOIs
Publication statusPublished - 1 Jul 2014
Externally publishedYes

Keywords

  • Hop-constraints
  • Integer programming
  • OR in telecommunications
  • Steiner tree

Fingerprint Dive into the research topics of 'Hop constrained Steiner trees with multiple root nodes'. Together they form a unique fingerprint.

Cite this