J. of Global Optimization, vol.17, pp. 267-283, 2000.
ABSTRACT
In this paper, we present a parallel greedy randomized
adaptive search procedure (GRASP) for the Steiner problem in
graphs. GRASP is a two phase metaheuristic. In the first
phase, solutions are constructed using a greedy randomized
procedure. Local search is applied in the second phase, leading to
a local minimum with respect to a specified neighborhood. In the
Steiner problem in graphs, feasible solutions can be characterized by
their non-terminal nodes (Steiner nodes) or by their key-paths.
According to this characterization, two GRASP procedures are described
using different local search strategies. Both use an identical
construction procedure. The first uses a node-based neighborhood
for local search, while the second uses a path-based neighborhood.
Computational results comparing the two procedures show that while the
node-based variant produces better quality solutions, the path-based
variant is about twice as fast. A hybrid GRASP procedure combining
the two neighborhood search strategies is then proposed.
Computational experiments with a parallel implementation of the hybrid
procedure are reported, showing that the algorithm found optimal
solutions for 45 out of 60 benchmark instances and was never off by more
than four percent of the optimal solution value. The average
speedup results observed for the test problems show that increasing the
number of processors reduces elapsed times with increasing
speedups. Moreover, the main contribution of the parallel
algorithm concerns the fact that larger speedups of the same order of
the number of processors are obtained exactly for the most difficult
problems.
PostScript file of full paper