Cohérence d'arc virtuelle pour les CSP pondérés

Résumé : L'optimisation d'une combinaison de fonctions de coût définies sur des variables discrètes est un problème central dans de nombreux formalismes tels que les réseaux probabilistes, le problème de satisfiabilité maximum, les réseaux de contraintes pondérés (WCSP) ou les graphes de facteurs. De récents résultats ont montré que la maintenance d'une forme de cohérence locale dans un algorithme de séparation-évaluation (Branch and Bound) fournit des minorants qui sont assez puissants pour résoudre de nombreuses instances réelles. Nous présentons ici la cohérence d'arc virtuelle (Virtual Arc Consistency, VAC) qui planifie et applique itérativement des séquences d'opération de propagation de coûts fractionnaires qui garantissent de transformer un WCSP en un autre WCSP équivalent incorporant un minorant accru. Bien que plus faible que l'arc cohérence optimale (OSAC) récemment proposée, VAC est plus rapide et est capable de résoudre le langage polynomial défini par des fonctions de coût sous-modulaires. Le maintien de VAC pendant la recherche conduit à d'importantes améliorations sur des problèmes difficiles de grande taille et nous a permis de clore deux instances bien connues du problème d'affectation de fréquence.
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.237-246, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00292640
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 11:20:35
Dernière modification le : jeudi 11 janvier 2018 - 06:21:34
Document(s) archivé(s) le : vendredi 28 mai 2010 - 23:03:58

Fichier

pages-237-246-article11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292640, version 1

Collections

Citation

Martin Cooper, Simon De Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki. Cohérence d'arc virtuelle pour les CSP pondérés. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.237-246, 2008. 〈inria-00292640〉

Partager

Métriques

Consultations de la notice

223

Téléchargements de fichiers

160