Efficient parallel cooperative implementations of GRASP heuristics

We propose a parallel cooperative strategy for the implementation of the GRASP metaheuristic and we illustrate it with a GRASP with path-relinking heuristic for the 2-path network design problem. Numerical results illustrating the effectiveness of the approach are reported. We comment in detail the implementation strategies that take most advantage of the algorithm structure. Computational experiments show linear speedups on a Linux cluster with 32 machines.