Inférence d'Inconsistances pour la Résolution de MAX-N CSP

Résumé : Le présent article porte sur la résolution exacte du problème de satisfaction maximale de contraintes (Max- CSP). La résolution du Max-CSP est généralement effectuée à l'aide d'algorithmes de type branch and bound. L'efficacité de ces algorithmes dépend étroitement de la borne inférieure de la valeur du Max-CSP qu'ils utilisent au cours de la recherche. Les bornes inférieures pour le Max-CSP se basent, en général, sur le concept d'arc consistance (AC). Nous présentons ici un mécanisme d'inférences d'inconsistance entre valeurs dans le but d'augmenter les valeurs des bornes inférieures basées sur l'AC. Ceci est eectué en détectant les inconsis- tances ignorées par les compteurs d'arc-inconsistance dirigée dac. L'inférence d'inconsistances pour une valeur a d'une variable non instanciée i, consiste à rajouter à la contribution de a le nombre de variables futures dont les valeurs participant au calcul de la borne inférieure sont incohérentes avec a. Une implémentation de cette technique est présentée et testée sur des Max-CSP aléa- toires.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00085789
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 10:50:12
Dernière modification le : jeudi 11 janvier 2018 - 06:17:31
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:08:49

Fichier

Identifiants

  • HAL Id : inria-00085789, version 1

Collections

Citation

Fayçal Djerourou, Hachemi Bennaceur. Inférence d'Inconsistances pour la Résolution de MAX-N CSP. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085789〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

37