Conflict history based heuristic for constraint satisfaction problem solving - Aix-Marseille Université Accéder directement au contenu
Article Dans Une Revue Journal of Heuristics Année : 2021

Conflict history based heuristic for constraint satisfaction problem solving

Djamal Habet
  • Fonction : Auteur
  • PersonId : 1090275

Résumé

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.
Fichier principal
Vignette du fichier
CHB.pdf (485.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03276535 , version 1 (02-07-2021)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More