HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Filtrage de fonctions de coût globales décomposables

David Allouche 1 Christian Bessière 2 Patrice Boizumault 3 Simon de Givry 1 Patricia Gutierrez Samir Loudni 3 Jean-Philippe Metivier 3 Thomas Schiex 1
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 Equipe CODAG - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image et Instrumentation de Caen
Abstract : As [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 achieves the same level of consistency on the original global cost function. We give conditions under which directional arc consistency and virtual arc consistency o er such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate e cient global cost functions in solvers.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

Contributor : Simon de Givry Connect in order to contact the contributor
Submitted on : Tuesday, April 9, 2013 - 6:51:00 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Monday, April 3, 2017 - 2:52:16 AM


Files produced by the author(s)


  • HAL Id : hal-00809789, version 1
  • PRODINRA : 316102


David Allouche, Christian Bessière, Patrice Boizumault, Simon de Givry, Patricia Gutierrez, et al.. Filtrage de fonctions de coût globales décomposables. 8èmes Journées Francophones de Programmation par Contraintes (JFPC 2012), May 2012, Toulouse, France. ⟨hal-00809789⟩



Record views


Files downloads