Geodesic
Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 87-103

Voir la notice de l'article provenant de la source Numdam

Nous présentons dans cet article un algorithme générique hybride permettant de combiner des méthodes complètes (programmation par contraintes) et incomplètes (recherche locale) pour la résolution de problèmes de satisfaction de contraintes. Ce schéma algorithmique basé sur la gestion de populations, utilise des techniques de propagation de contraintes intégrant également des heuristiques de recherche locale. Les structures utilisées autorisent une interaction homogène entre les différentes méthodes mises en œuvre et permettent également de bénéficier de leurs atouts respectifs. Nous proposons alors diverses stratégies de combinaisons dont nous mettons en avant l'intérêt sur quelques exemples par le biais d'une implémentation.

In this paper, we present a generic hybrid algorithm for combining complete (constraint programming) and incomplete (local search) methods in order to solve constraint satisfaction problems. This algorithmic scheme uses constraint propagation techniques and local search heuristics over populations. The structures involved provide an harmonious interaction between the different methods, and also benefit from the respective methods' assets. We propose various combination strategies and emphasize their interest on some examples which are solved by means of an implementation.

DOI : 10.1051/ro:2005006
Keywords: satisfaction de contraintes, propagation de contraintes, méthodes de recherche hybride 
@article{RO_2005__39_2_87_0,
     author = {Deleau, Herv\'e and Hao, Jin-Kao and Saubion, Fr\'ed\'eric},
     title = {Algorithmes hybrides g\'en\'eriques pour la r\'esolution de probl\`emes de satisfaction de contraintes},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {87--103},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {2},
     year = {2005},
     doi = {10.1051/ro:2005006},
     mrnumber = {2181793},
     zbl = {1104.90056},
     language = {fr},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2005006/}
}
TY  - JOUR
AU  - Deleau, Hervé
AU  - Hao, Jin-Kao
AU  - Saubion, Frédéric
TI  - Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2005
SP  - 87
EP  - 103
VL  - 39
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2005006/
DO  - 10.1051/ro:2005006
LA  - fr
ID  - RO_2005__39_2_87_0
ER  - 
%0 Journal Article
%A Deleau, Hervé
%A Hao, Jin-Kao
%A Saubion, Frédéric
%T Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2005
%P 87-103
%V 39
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2005006/
%R 10.1051/ro:2005006
%G fr
%F RO_2005__39_2_87_0
Deleau, Hervé; Hao, Jin-Kao; Saubion, Frédéric. Algorithmes hybrides génériques pour la résolution de problèmes de satisfaction de contraintes. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 87-103. doi: 10.1051/ro:2005006

Cité par Sources :