Relaxation de AllDifferent avec préférences

National audienceDans cet article, nous proposons deux nouvelles sémantiques de violation pour la contrainte globale AllDifferent permettant de prendre en compte les préférences formulées par l'utilisateur. La première, dite sémantique basée variable, pour laquelle un poids est attribué à chaque variable et où la quantité de violation correspond à la somme des poids des variables à réinstancier. Pour cette sémantique, nous proposons un algorithme maintenant la consistance globale en temps polynomial. La seconde, dite sémantique basée décomposition, pour laquelle un poids est attribué à chaque contrainte binaire de différence et où la quantité de violation correspond à la somme des poids des contraintes binaires de différence insatisfaites. Pour cette sémantique, nous montrons que le test de consistance est un problème NP-Complet. Nous proposons alors de maintenir une consistance locale basée sur le calcul d'un minorant (en temps polynomial) et nous étudions expérimentalement la qualité du minorant et de la consistance ainsi maintenue