Paper Info
Title
An exact algorithm for the node weighted Steiner tree problem
Abstract
.  The Node Weighted Steiner Tree Problem (NW-STP) is a generalization of the Steiner Tree Problem. A lagrangean heuristic presented in EngevallS: StrLBN: 98, and based on the work in Lucena: 92, solves the problem by relaxing an exponential family of generalized subtour elimination constraints and taking into account only the violated ones as the computation proceeds. In EngevallS: StrLBN: 98 the computational results refer to complete graphs up to one hundred vertices. In this paper, we present a branch-and-bound algorithm based on this formulation. Its performance on the instances from the literature confirms the effectiveness of the approach. The experimentation on a newly generated set of benchmark problems, more similar to the real-world applications, shows that the approach is still valid, provided that suitable refinements on the bounding procedures and a preprocessing phase are introduced. The algorithm solves to optimality all of the considered instances up to one thousand vertices, with the exception of 11 hard instances, derived from the literature of a similar problem, the Prize Collecting Steiner Tree Problem.
Year
DOI
Venue
2006
10.1007/s10288-005-0081-y
4OR
Keywords
Field
DocType
relax-and-cut,prize collecting,steiner problem,complete graph,steiner tree problem,exponential family,branch and bound algorithm
Discrete mathematics,Mathematical optimization,Combinatorics,Heuristic,Exact algorithm,Vertex (geometry),Steiner tree problem,Exponential family,Preprocessor,Mathematics,Computation,Bounding overwatch
Journal
Volume
Issue
ISSN
4
2
1614-2411
Citations 
PageRank 
References 
2
0.46
11
Authors
2
Name
Order
Citations
PageRank
Roberto Cordone131028.87
Marco Trubian259451.20