Relaxation de AllDifferent avec préférences

Jean-Philippe Metivier 1 Patrice Boizumault 1 Samir Loudni 1
1 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Résumé : Dans 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.
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.191-200, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00291577
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 15:05:17
Dernière modification le : mardi 5 juin 2018 - 10:14:40
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:56:12

Fichier

pages-191-200-article19.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291577, version 1

Citation

Jean-Philippe Metivier, Patrice Boizumault, Samir Loudni. Relaxation de AllDifferent avec préférences. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.191-200, 2008. 〈inria-00291577〉

Partager

Métriques

Consultations de la notice

199

Téléchargements de fichiers

185