Cohérences et dichotomies parmi des CSP pondérés

Abstract : Nous considérons des CSP pondérés dans un cadre de restrictions de contraintes pondérées. Plus précisément, nous fixons un ensemble de fonctions de coût, appelé le langage de contraintes, et on considère le problème de minimiser une somme de contraintes pondérées o`u les fonctions de coût viennent du langage. On se restreint à l’étude des fonctions de coût qui prennent des valeurs rationnelles ou l’infini positif. En particulier, ce problème permet de modéliser deux types de problème d’optimisation classiques sur des instances de CSP : — Min CSP où l’objectif est de minimiser le nombre de contraintes non satisfaites ; — Min Sol où l’objectif est de minimiser une fonction objectif sur l’ensemble d’affectations satisfaisantes. On s’intéresse à la question suivante : pour quels langages, le problème peut-il être résolu en temps polynomial ? Les notions de cohérence en général et la cohérence d’arc en particulier sont des outils de base pour les solveurs et pour l’étude des classes polynomiales. Notre étude démarre avec la notion de cohérence d’arc d’un réseau de contraintes classique. Cette notion et ses généralisations nous amènent ensuite aux notions correspondantes des CSP pondérés, où il s’avère que ces notions donnent une réponse presque exhaustive à notre question ci-dessus.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-01730648
Contributor : Admin Upem <>
Submitted on : Tuesday, March 13, 2018 - 2:34:00 PM
Last modification on : Thursday, July 5, 2018 - 2:45:49 PM

Identifiers

  • HAL Id : hal-01730648, version 1

Citation

Johan Thapper. Cohérences et dichotomies parmi des CSP pondérés. JFPC 2016 : Actes des Douzièmes Journées Francophones de Programmation par Contraintes, Jun 2016, Montpellier, France. pp.16-17. ⟨hal-01730648⟩

Share

Metrics

Record views

34