Skip to Main content Skip to Navigation
New interface
Conference papers

Filtering decomposable global cost functions

Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Wednesday, June 3, 2020 - 12:23:54 PM
Last modification on : Friday, November 18, 2022 - 4:12:59 AM


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


David Allouche, Christian Bessière, 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⟩



Record views