Filtering decomposable global cost functions - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 2012

Filtering decomposable global cost functions


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.
No file

Dates and versions

hal-02747813 , version 1 (03-06-2020)


  • HAL Id : hal-02747813 , version 1
  • PRODINRA : 259129


David Allouche, Christian Bessiere, Patrice Boizumault, Simon de Givry, Patricia Gutierrez, et al.. Filtering decomposable global cost functions. Twenty-Sixth Conference on Artificial Intelligence, Jul 2012, Toronto, Canada. pp.7. ⟨hal-02747813⟩
19 View
0 Download


Gmail Facebook X LinkedIn More