ALCOMFT-TR-01-155

M.J. Blesa, Ll. Hernandez and F. Xhafa
Parallel Skeletons for Tabu Search Method Based on Search Strategies and Neighborhood Partition
Barcelona. Work package 4. June 2001.

Abstract: In this paper we present two parallel skeletons for Tabu Search method -a well known meta-heuristic for approximately solving combinatorial optimization problems. Our parallel skeletons are designed and implemented using the generic parallel programming paradigm. The first skeleton is based on independent runs model with search strategies while the second is a master-slave model with neighborhood partition. Our starting point to obtain these skeletons was the design and implementation of a sequential skeleton that was used later as basis for the two parallel skeletons. Both skeletons provide the user with the followings: (a) permit to obtain parallel implementations of tabu search method for concrete combinatorial optimization problems from existing sequential implementations; (b) there is no need for the user to know neither parallel programming nor communication libraries; (c) the parallel implementation for a concrete problem is obtained automatically from the existing sequential implementation of the problem. The skeletons are implemented in C++ using MPI as a communication library and offer several properties such as a genericity, flexibility, component reuse, robustness and time savings, mainly due to the generic and object oriented programming paradigms. We have instantiated the two skeletons for the 0-1 Multidimensional Knapsack problem and report extensive experimental results.

Postscript file: ALCOMFT-TR-01-155.ps.gz (111 kb).