Filtering Decomposable Global Cost Functions

As (Lee and Leung 2012) have shown, weighted constraint satisfaction problems can benefit 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 achieves the same level of consistency on the original global cost function. We give conditions under which directional and virtual arc consistency offer such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate efficient global cost functions in solvers.

Authors

• David Allouche Institut National de la Recherche Agronomique
• Christian Bessiere
• Patrice Boizumault University of Caen
• Simon de Givry Institut National de la Recherche Agronomique
• Patricia Gutierrez IIIA-CSIC, University of Autonomade Barcelona
• Samir Loudni University of Caen
• Jean-Philippe Métivier University of Caen
• Thomas Schiex Institut National de la Recherche Agronomique

Keywords

No keywords are indexed for this paper.