Reactive Tabu Search with Path-Relinking for the Steiner Problem in Graphs

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists in finding a minimum weight subgraph spanning a given subset of nodes (terminals) of the original graph. We describe a reactive tabu search with path-relinking algorithm for the Steiner problem in graphs, based on the extension of a previously developed tabu search algorithm using a neighborhood defined by insertions and eliminations of Steiner nodes. Computational experiments on benchmark problems are reported, comparing the reactive tabu search with other metaheuristic implementations. The reactive tabu search algorithm outperforms other algorithms, obtaining better or comparably good solutions. We also describe a robust parallel implementation based on an independent-thread multiple-walk strategy and report improved computational results on a 32-processor cluster running under Linux.