Une technique de décomposition pour Max-CSP

Résumé : L'objectif du problème Max-CSP (Maximal Constraint Satisfaction Problem) est de trouver une instanciation qui minimise le nombre de contraintes violées dans un réseau de contraintes. Dans cet article, à partir du concept de contraintes disjonctives inférées introduit par Freuder et Hubbe, nous montrons qu'il est possible d'exploiter les compteurs d'arc-incohérence, associés à chaque valeur du réseau, de manière à éviter l'exploration de parties inutiles de l'espace de recherche. Le principe est de raisonner à partir de la distance entre les deux meilleures valeurs du domaine d'une variable, selon ces compteurs. Sur cette base, on peut mettre en place une technique de décomposition qui peut être utilisée tout au long de la recherche de manière à réduire le problème courant en sous-problèmes plus simples. Il est intéressant de noter que cette approche ne dépend pas de la structure du graphe de contraintes, comme cela est généralement proposé. Comme alternative à la décomposition, il est possible de poster des contraintes dures qui peuvent être utilisées pour élaguer l'espace de recherche. L'intérêt de notre approche est illustré en pratique, avec cette alternative, par une expérimentation basée sur un algorithme classique de séparation et évaluation, à savoir PFC-MRDAC.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.219-226, 2008
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291628
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 16:14:35
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:56:38

Fichier

pages-219-226-article22.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291628, version 1

Collections

Citation

Hachémi Bennaceur, Christophe Lecoutre, Olivier Roussel. Une technique de décomposition pour Max-CSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.219-226, 2008. 〈inria-00291628〉

Partager

Métriques

Consultations de la notice

108

Téléchargements de fichiers

96