Substituabilité au voisinage pour le cadre WCSP - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Substituabilité au voisinage pour le cadre WCSP

Résumé

WCSP is an optimization problem for which many forms of soft local (arc) consistencies such as existential directional arc consistency (EDAC) and virtual arc consistency (VAC) have been proposed these last years. In this paper, we adopt a different perspective by revisiting the well-known property of (soft) substitutability. First, we provide a clear picture of the relationships existing between soft neighborhood substitutability (SNS) and a tractable property called $pcost$ which is based on the concept of overcost of values (through the use of so-called cost pairs). We prove that under certain assumptions, $pcost$ is equivalent to SNS but weaker than SNS in the general case since we show that SNS is coNP-hard. We also show that SNS preserves the property VAC but not the property EDAC. Finally, we introduce an optimized algorithm and we show on various series of WCSP instances, the practical interest of maintaining $pcost$ together with AC*, FDAC or EDAC, during search.
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.
Fichier principal
Vignette du fichier
subFinalJFPC2012.pdf (180.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00818527 , version 1 (29-04-2013)

Identifiants

  • HAL Id : hal-00818527 , version 1

Citer

Christophe Lecoutre, Djamel-Eddine Dehani, Olivier Roussel. Substituabilité au voisinage pour le cadre WCSP. JFPC - Huitièmes Journées Francophones de Programmation par Contraintes - 2012, Apr 2013, Toulouse, France. ⟨hal-00818527⟩
132 Consultations
81 Téléchargements

Partager

Gmail Facebook X LinkedIn More