Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Thursday, April 4, 2019 - 10:04:27 PM
Last modification on : Wednesday, November 3, 2021 - 5:50:33 AM


Files produced by the author(s)


  • HAL Id : hal-02090610, version 1



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⟩



Record views


Files downloads