Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6897491 | European Journal of Operational Research | 2014 | 13 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Luis Gouveia, Markus Leitner, Ivana LjubiÄ,