Experiments in Parallel Constraint-Based Local Search

Yves Caniou 1 Philippe Codognet 2 Daniel Diaz 3 Salvador Abreu 4
1 LIP - Laboratoire de l'Informatique du Parallélisme
2 LIP6 - Laboratoire d'Informatique de Paris 6
3 CRI - Centre de Recherche en Informatique de Paris 1
4 CENTRIA - Centre for Artificial Intelligence
Abstract : We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hardware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the "adaptive search" method, an efficient sequential local search method for Constraint Satisfaction Problems. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the simultaneous computations. Preliminary performance evaluation on a variety of classical CSPs benchmarks shows that speedups are very good for a few tens of processors, and good up to a few hundreds of processors.
Type de document :
Communication dans un congrès
11th European conference on Evolutionary computation in combinatorial optimization (EvoCOP'11), Apr 2011, Torino, Italy. Springer, 6622, pp.96-107, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-20364-0_9〉
Liste complète des métadonnées
https://hal-paris1.archives-ouvertes.fr/hal-00663789
Contributeur : Daniel Diaz <>
Soumis le : vendredi 27 janvier 2012 - 15:23:21
Dernière modification le : jeudi 22 novembre 2018 - 14:04:21

Lien texte intégral

openaccess

Identifiants

Collections

ENS-LYON | CRI | INRIA | UNIV-PARIS1 | LIP | UPMC | LIP6 | UNIV-LYON1 | SORBONNE-UNIVERSITE

Citation

Yves Caniou, Philippe Codognet, Daniel Diaz, Salvador Abreu. Experiments in Parallel Constraint-Based Local Search. 11th European conference on Evolutionary computation in combinatorial optimization (EvoCOP'11), Apr 2011, Torino, Italy. Springer, 6622, pp.96-107, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-20364-0_9〉. 〈hal-00663789〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

160

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD