TitleFiltering Decomposable Global Cost Functions
Publication TypeConference Paper
Year of Publication2012
AuthorsAllouche D, Bessière C, Boizumault P, de Givry S, Gutierrez P, Loudni S, Métivier J-P, Schiex T
Conference Name26th AAAI Conference on Artificial Intelligence (AAAI 2012)
Conference LocationToronto, Canada
Date Published22/07/2012

As (Lee and Leung 2009; 2010) 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 offers guarantees on the level of consistency enforced on the original global cost function. We show that directional arc consistency 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.