Skip to Main content Skip to Navigation
Conference papers

Conflict History based Search for Constraint Satisfaction Problem

Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : Branching heuristic is an important module in algorithms dedicated to solve Constraint Satisfaction Problems (CSP). It impacts the efficiency of exploring the search space and exploiting the problem structure. In this paper, we propose Conflict-History Search (CHS), a dynamic and adaptive branching heuristic for CSP solving. It is based on the search failures and considers the temporality of these failures throughout the resolution process. The exponential recency weighted average is used to estimate the evolution of the hardness of constraints throughout the search. The experimental evaluation on XCSP3 instances shows that integrating CHS to solvers based on MAC obtains competitive results and can improve those obtained by other heuristics of the state of the art, such as dom/wdeg and ABS.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02090618
Contributor : Cyril Terrioux <>
Submitted on : Wednesday, May 20, 2020 - 7:06:27 PM
Last modification on : Friday, May 22, 2020 - 10:46:39 AM

File

article.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Djamal Habet, Cyril Terrioux. Conflict History based Search for Constraint Satisfaction Problem. Proceedings of the 34th ACM/SIGAPP Symposium On Applied Computing (SAC), Apr 2019, Limassol, Cyprus. ⟨10.1145/3297280.3297389⟩. ⟨hal-02090618⟩

Share

Metrics

Record views

154

Files downloads

83