Conflict History Based Branching Heuristic for CSP Solving

Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : An important feature in designing algorithms to solve Constraint Satisfaction Problems (CSP) is the definition of a branching heuristic to explore efficiently the search space and exploit the problem structure. We propose Conflict-History Search (CHS), a new dynamic and adaptive branching heuristic for CSP solving. It is based on the search history by considering the temporality of search failures. To achieve that, we use the exponential recency weighted average 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 through other heuristics of the state of the art.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02090610
Contributor : Cyril Terrioux <>
Submitted on : Thursday, April 4, 2019 - 10:04:27 PM
Last modification on : Sunday, June 23, 2019 - 5:54:02 PM

File

CIMA2018_paper_6.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02090610, version 1

Collections

Citation

Djamal Habet, Cyril Terrioux. Conflict History Based Branching Heuristic for CSP Solving. Proceedings of the 8th International Workshop on Combinations of Intelligent Methods and Applications (CIMA), Nov 2018, Volos, Greece. ⟨hal-02090610⟩

Share

Metrics

Record views

43

Files downloads

32