Flexible cooperation in parallel local search

Constraint-Based Local Search (CBLS) consist in using Local Search methods [4] for solving Constraint Satisfaction Problems (CSP). In order to further improve the performance of Local Search, one possible option is to take advantage of the increasing availability of parallel computational resources. Parallel implementation of local search meta-heuristics has been studied since the early 90's, when multiprocessor machines started to become widely available, see [6]. One usually distinguishes between single-walk and multiple-walk methods: Single-walk methods consist in using parallelism inside a single search process, e.g. for parallelizing the exploration of the neighborhood, while multiple-walk methods (also called multi-start methods) consist in developing concurrent explorations of the search space, either independently (IW) or cooperatively (CW) with some communication between concurrent processes. Although good results can be achieved just with IW [1], a more sophisticated paradigm featuring cooperation between independent walks should bring better performance. We thus propose a general framework for cooperative search, which defines a flexible and parametric strategy based on the cooperative multi-walk (CW) scheme. The framework is oriented towards distributed architectures based on clusters of nodes, with the notion of "teams" running on nodes which group several individual search engines (e.g. multicore nodes). The idea is that teams are distributed and thus have limited inter-node communication. This framework allows the programmer to define aspects such as the degree of intensification and diversification present in the parallel search process. A good trade-off is essential to reach high performance. A preliminary implementation of the general CW framework has been done in the X10 programming language [5], and performance evaluation over a set of well-known benchmark CSPs shows that CW consistently outperforms IW.