Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Cooperation control in Parallel SAT Solving: a Multi-armed Bandit Approach

Nadjib Lazaar 1, 2, * Youssef Hamadi 1, 3, 4 Said Jabbour 5 Michèle Sebag 6 
* Corresponding author
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In recent years, Parallel SAT solvers have leveraged with the so called Parallel Portfolio architecture. In this setting, a collection of independent Conflict-Directed Clause Learning (CDCL) algorithms compete and cooperate through Clause Sharing. However, when the number of cores increases, systematic clause sharing between CDCLs can slow down the search performance. Previous work has shown how the efficiency of the approach can be improved through controlling dynamically the amount of information shared by the cores [Hamadi et al., IJCAI09], specifically the allowed length of the shared clauses. In the present paper, a new approach is used to control the cooperation topology (pairs of units able to exchange clauses). This approach, referred to as Bandit Ensemble for parallel SAT Solving (BESS), relies on a multi-armed bandit formalization of the cooperation choices. BESS is empirically validated on the recent 2012 SAT challenge benchmark.
Document type :
Reports (Research report)
Complete list of metadata

https://hal.inria.fr/hal-00733282
Contributor : Nadjib Lazaar Connect in order to contact the contributor
Submitted on : Monday, December 17, 2012 - 5:54:04 PM
Last modification on : Friday, November 18, 2022 - 9:28:38 AM
Long-term archiving on: : Sunday, December 18, 2016 - 4:14:23 AM

Files

RR-8070.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00733282, version 2

Citation

Nadjib Lazaar, Youssef Hamadi, Said Jabbour, Michèle Sebag. Cooperation control in Parallel SAT Solving: a Multi-armed Bandit Approach. [Research Report] RR-8070, INRIA. 2012, pp.18. ⟨hal-00733282v2⟩

Share

Metrics

Record views

478

Files downloads

454