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
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

Contributor : Cyril Terrioux Connect in order to contact the contributor
Submitted on : Friday, July 2, 2021 - 11:07:13 AM
Last modification on : Friday, April 1, 2022 - 3:45:02 AM
Long-term archiving on: : Sunday, October 3, 2021 - 6:39:45 PM


Files produced by the author(s)




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



Record views


Files downloads