Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291577
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 3:05:17 PM
Last modification on : Thursday, February 7, 2019 - 5:47:40 PM
Long-term archiving on: : Friday, May 28, 2010 - 10:56:12 PM

File

pages-191-200-article19.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291577, version 1

Citation

Jean-Philippe Metivier, Patrice Boizumault, Samir Loudni. Relaxation de AllDifferent avec préférences. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.191-200. ⟨inria-00291577⟩

Share

Metrics

Record views

231

Files downloads

274