Consistencies and dichotomies among weighted CSPs
Cohérences et dichotomies parmi des CSP pondérés
Résumé
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.