Substituabilité au voisinage pour le cadre WCSP

Résumé : WCSP est un problème d'optimisation pour lequel plusieurs formes de cohérences locales souples telles que, par exemple, la cohérence d'arc existentielle directionnelle (EDAC) et la cohérence d'arc virtuelle (VAC) ont été proposées durant ces dernières années. Dans cet article, nous adoptons une perspective différente en revisitant la propriété bien connue de la substituabilité (souple). Tout d'abord, nous précisons les relations existant entre la substituabilité de voisinage souple (SNS pour Soft Neighbourhood Substitutability) et une propriété appelée $pcost$ qui est basée sur le concept de surcoût de valeurs (par le biais de l'utilisation de paires de surcoût). Nous montrons que sous certaines hypothèses, $pcost$ est équivalent à SNS, mais que dans le cas général, elle est plus faible que SNS prouvée être coNP-difficile. Ensuite, nous montrons que SNS conserve la propriété VAC, mais pas la propriété EDAC. Enfin, nous introduisons un algorithme optimisé et nous montrons sur diverses séries d'instances WCSP l'intérêt pratique du maintien de $pcost$ avec AC*, FDAC ou EDAC, au cours de la recherche.
Type de document :
Communication dans un congrès
JFPC - Huitièmes Journées Francophones de Programmation par Contraintes - 2012, Apr 2013, Toulouse, France. 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00818527
Contributeur : Djamel-Eddine Dehani <>
Soumis le : lundi 29 avril 2013 - 13:26:26
Dernière modification le : jeudi 11 janvier 2018 - 06:22:37
Document(s) archivé(s) le : lundi 19 août 2013 - 09:46:33

Fichier

subFinalJFPC2012.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00818527, version 1

Collections

Citation

Christophe Lecoutre, Olivier Roussel, Djamel-Eddine Dehani. Substituabilité au voisinage pour le cadre WCSP. JFPC - Huitièmes Journées Francophones de Programmation par Contraintes - 2012, Apr 2013, Toulouse, France. 2012. 〈hal-00818527〉

Partager

Métriques

Consultations de la notice

177

Téléchargements de fichiers

76