Skip to Main content Skip to Navigation
Journal articles

Conflict history based heuristic for constraint satisfaction problem solving

Djamal Habet 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : The variable ordering heuristic is an important module in algorithms dedicated to solve Constraint Satisfaction Problems (CSP), while it impacts the efficiency of exploring the search space and the size of the search tree. It also exploits, often implicitly, the structure of the instances. In this paper, we propose Conflict-History Search (CHS), a dynamic and adaptive variable ordering heuristic for CSP solving. It is based on the search failures and considers the temporality of these failures throughout the solving steps. 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 (Maintaining Arc Consistency) and BTD (Backtracking with Tree Decomposition) achieves competitive results and improvements compared to the state-of-the-art heuristics. Beyond the decision problem, we show empirically that the solving of the constraint optimization problem (COP) can also take advantage of this heuristic.
Document type :
Journal articles
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03276535
Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Friday, July 2, 2021 - 11:07:13 AM
Last modification on : Saturday, July 3, 2021 - 3:46:12 AM
Long-term archiving on: : Sunday, October 3, 2021 - 6:39:45 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-12-30

Please log in to resquest access to the document

Identifiers

Collections

Citation

Djamal Habet, Cyril Terrioux. Conflict history based heuristic for constraint satisfaction problem solving. Journal of Heuristics, Springer Verlag, 2021, ⟨10.1007/s10732-021-09475-z⟩. ⟨hal-03276535⟩

Share

Metrics

Record views

61