Filtering decomposable global cost functions
2011
Allouche , David (INRA , Auzeville (France). UR 0875 Unité de recherche Biométrie et Intelligence Artificielle) | Bessière , Christian (Centre National de la Recherche Scientifique, Montpellier(France). UMR5506 Laboratoire d'informatique, de robotique et de microélectronique de Montpellier (LIRMM)) | Boizumault , Patrice (Centre National de la Recherche Scientifique, Caen(France). UMR6072 Groupe de REcherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC) ) | De Givry , Simon (INRA , Auzeville (France). UR 0875 Unité de recherche Biométrie et Intelligence Artificielle) | Gutierrez , P. (Consejo Superior de Investigaciones Científicas, Bellaterra(Espagne). Campus Universitat Aut onoma de Barcelona) | Loudni , Samir (Centre National de la Recherche Scientifique, Caen(France). UMR6072 Groupe de REcherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC)) | Métivier , J.P. (Centre National de la Recherche Scientifique, Caen(France). UMR6072 Groupe de REcherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC)) | Schiex , Thomas (INRA , Auzeville (France). UR 0875 Unité de recherche Biométrie et Intelligence Artificielle)
法语. Comme l'ont montrée [19, 18], les réseaux de fonctions de coût (ou CSP pondérés) peuvent bénéficier de l'introduction de fonctions de coût globales, amenant à la construction d'outils de "Programmation par Fonctions de Coût", généralisant la "Programmation par Contraintes". Dans cet article, nous explorons la possibilité de décomposer des fonctions de coût globales de façon à ce que l'établissement de cohérence locales souples sur la décomposition garantisse qu'un certain niveau de service soit également établi sur la fonction de coût globale d'origine. Nous montrons que la cohérence d'arc directionnelle ainsi que la cohérence d'arc virtuelle permettent d'offrir de telles garanties. Nous concluons par différentes expérimentations sur des fonctions de coûts globales qui montrent que de telles décompositions sont fort utiles pour intégrer de façon très simple des fonctions de coût, efficacement traitées, dans les outils de résolution.
显示更多 [+] 显示较少 [-]英语. As [19, 18] have shown, weighted constraint satisfaction problems can bene t from the introduction of global cost functions, leading to a new Cost Function Programming paradigm. In this paper, we explore the possibility of decomposing global cost functions in such a way that enforcing soft local consistencies on the decomposition o ers guarantees on the level of consistency enforced on the original global cost function. We show that directional arc consistency and virtual arc consistency o er such guarantees.We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate e cientglobal cost functions in solvers.
显示更多 [+] 显示较少 [-]