Filtering decomposable global cost functions
Résumé
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 experimention decomposable cost functions showing that decompo- sitions may be very useful to easily integrate e cient global cost functions in solvers.