Communication Issues in Designing Cooperative Multi-Thread Parallel Searches

Roughly speaking, parallel local search techniques can be divided into three categories: low-level parallelization strategies (e.g., master-slave schemes), solution-space partitioning methods and multi-thread procedures in which several processes explore concurrently the same search space. The multi-thread technique can be further subdivided into independent and cooperative search thread algorithms. In this paper, we focus on cooperative multi-thread heuristics applied to methods such as tabu search, and attempt to identify the key questions to be addressed in the design of any algorithm in this class. In particular, we show that questions related to inter-agent communications are a central element of the algorithmic design of these methods.