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, Automatique 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

https://hal.inria.fr/hal-00809789
Contributor : Simon de Givry <>
Submitted on : Tuesday, April 9, 2013 - 6:51:00 PM
Last modification on : Tuesday, February 16, 2021 - 3:30:33 AM
Long-term archiving on: : Monday, April 3, 2017 - 2:52:16 AM

File

Givry12a.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

486

Files downloads

547