Improving Parallel Local Search for SAT

Abstract : In this work, our objective is to study the impact of knowledge sharing on the performance of portfolio-based parallel local search algorithms. Our work is motivated by the demonstrated importance of clause-sharing in the performance of complete parallel SAT solvers. Unlike complete solvers, state-of-the-art local search algorithms for SAT are not able to generate redundant clauses during their execution. In our settings, each member of the portfolio shares its best configuration (i.e., one which minimizes conflicting clauses) in a common structure. At each restart point, instead of classically generating a random configuration to start with, each algorithm aggregates the shared knowledge to carefully craft a new starting point. We present several aggregation strategies and evaluate them on a large set of problems.
Type de document :
Communication dans un congrès
Learning and Intelligent OptimizatioN Conference LION5, Jan 2011, Rome, Italy. 2011
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00563775
Contributeur : Alejandro Arbelaez <>
Soumis le : lundi 7 février 2011 - 11:39:20
Dernière modification le : lundi 7 février 2011 - 11:52:26
Document(s) archivé(s) le : dimanche 8 mai 2011 - 03:26:13

Fichier

lion-sat.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00563775, version 1

Collections

Citation

Alejandro Arbelaez, Youssef Hamadi. Improving Parallel Local Search for SAT. Learning and Intelligent OptimizatioN Conference LION5, Jan 2011, Rome, Italy. 2011. 〈inria-00563775〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

193