La substituabilité et la cohérence de tuples pour les réseaux de contraintes pondérées
- PhD Student:
- Djamel-Eddine Dehani
- Advisor :
- Christophe Lecoutre
- Co-Supervisor :
- Olivier Roussel
- Funding : Artois, Région HdF
- PhD defended on :
- Feb 13, 2014 • Salle des thèses
Résumé
Cette thèse se situe dans le domaine de la programmation par contraintes (CP). Plus précisément, nous nous intéressons au problème de satisfaction de contraintes pondérées (WCSP), qui 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 ce cadre, nous adoptons une perspective différente en revisitant la propriété bien connue de la substituabilité. Tout d’abord, nous précisons les relations existant entre la substituabilité de voisinage souple (SNS) 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. Nous introduisons un algorithme optimisé et nous étudions la relation existante entre SNS et les différentes cohérences. Nous présentons aussi un nouveau type de propriétés pour les WCSPs. Il s’agit de la cohérence de tuples (TC) dont l’établissement sur un WCN est effectué grâce à une nouvelle opération appelée TupleProject. Nous proposons également une version optimale de cette propriété, OTC, qui peut être perçue comme une généralisation de OSAC (Optimal Soft Arc +Consistency). Enfin, nous étendons la notion de substituabilité souple aux tuples.