Article ID: | iaor20071446 |
Country: | France |
Volume: | 39 |
Issue: | 1 |
Start Page Number: | 55 |
End Page Number: | 74 |
Publication Date: | Jan 2005 |
Journal: | RAIRO Operations Research |
Authors: | Pralet Cdric, Verfaillie Grard |
Keywords: | heuristics |
The decision repair algorithm, which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments, or (iii) as a hybridisation between local search and constraint propagation. Experiments reported by Pralet and Verfaillie show that some heuristics for the choice of the variable to which to backtrack behave well on consistent instances and that other heuristics behave well on inconsistent ones. They show also that, despite its