Skip to Main content Skip to Navigation
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

https://hal.inrae.fr/hal-02747813
Contributor : Migration Prodinra <>
Submitted on : Wednesday, June 3, 2020 - 12:23:54 PM
Last modification on : Wednesday, April 21, 2021 - 11:08:03 AM

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

14