Voir la notice de l'article provenant de la source Numdam
The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence 139 (2002) 21-45), 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 in Pralet and Verfailllie (2004) 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 a priori incompleteness, decision repair, equipped with some specific heuristics, can solve within a limited time almost all the consistent and inconsistent randomly generated instances over the whole constrainedness spectrum. In this paper, we discuss the heuristics that could be used by decision repair to solve consistent instances, on the one hand, and inconsistent ones, on the other hand. Moreover, we establish that some specific heuristics make decision repair complete.
@article{RO_2005__39_1_55_0,
author = {Pralet, C\'edric and Verfaillie, G\'erard},
title = {About the choice of the variable to unassign in a decision repair algorithm},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {55--74},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
doi = {10.1051/ro:2005001},
mrnumber = {2166345},
zbl = {1102.90035},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2005001/}
}
TY - JOUR AU - Pralet, Cédric AU - Verfaillie, Gérard TI - About the choice of the variable to unassign in a decision repair algorithm JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2005 SP - 55 EP - 74 VL - 39 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2005001/ DO - 10.1051/ro:2005001 LA - en ID - RO_2005__39_1_55_0 ER -
%0 Journal Article %A Pralet, Cédric %A Verfaillie, Gérard %T About the choice of the variable to unassign in a decision repair algorithm %J RAIRO - Operations Research - Recherche Opérationnelle %D 2005 %P 55-74 %V 39 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2005001/ %R 10.1051/ro:2005001 %G en %F RO_2005__39_1_55_0
Pralet, Cédric; Verfaillie, Gérard. About the choice of the variable to unassign in a decision repair algorithm. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 1, pp. 55-74. doi: 10.1051/ro:2005001
Cité par Sources :