HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Un bandit manchot pour combiner CHB et VSIDS

Mohamed Sami Cherif 1 Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Résumé : Les solveurs Conflict Driven Clause Learning (CDCL) sont efficaces pour résoudre des instances structurées avec un grand nombre de variables et de clauses. Un composant important de ces solveurs est l'heuristique de branchement qui sélectionne la prochaine variable de décision. Dans cet article, on propose d'utiliser un bandit manchot pour combiner deux heuristiques de l'état de l'art pour SAT, à savoir Variable State Independent Decaying Sum (VSIDS) et Conflict History-Based (CHB). Le bandit évalue et choisit de manière adaptative une heuristique adéquate à chaque redémarrage. Une évaluation expérimentale est menée et montre que la combinaison de VSIDS et CHB avec un bandit est compétitive et surpasse les deux heuristiques.
Document type :
Conference papers
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03270931
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Friday, June 25, 2021 - 11:15:31 AM
Last modification on : Tuesday, October 19, 2021 - 10:50:59 PM
Long-term archiving on: : Sunday, September 26, 2021 - 9:19:51 PM

File

jfpc2021d.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03270931, version 1

Collections

Citation

Mohamed Sami Cherif, Djamal Habet, Cyril Terrioux. Un bandit manchot pour combiner CHB et VSIDS. Actes des 16èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2021, Nice, France. ⟨hal-03270931⟩

Share

Metrics

Record views

84

Files downloads

7