Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291628
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 4:14:35 PM
Last modification on : Wednesday, June 2, 2021 - 10:50:50 AM
Long-term archiving on: : Friday, May 28, 2010 - 10:56:38 PM

File

pages-219-226-article22.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291628, version 1

Collections

Citation

Hachémi Bennaceur, Christophe Lecoutre, Olivier Roussel. Une technique de décomposition pour Max-CSP. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.219-226. ⟨inria-00291628⟩

Share

Metrics

Record views

146

Files downloads

199