Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Decomposing global cost functions

Abstract : Similarly to what has been done with Global Constraints in Constraint Programming, di erent results have been recently published on Global Cost Functions in weighted CSPs, de ning the premises of a Cost Function Programming paradigm. In this paper, in the spirit of Berge-acyclic decompositions of global constraints such as Regular, we explore the possibility of decomposing Global Cost Functions in such a way that enforcing soft local consistencies on the decomposed cost function o ers guarantees on the level of consistency enforced on the original global cost function. We show that an extension of Directional Arc Consistency to arbitrary arities and Virtual Arc Consistency o er speci c guarantees.We conclude by preliminary experiments on WeightedRegular decompositions that show that decompositions may be very useful to easily integrate global cost functions in existing solvers with good e fficiency.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.inrae.fr/hal-02747863
Déposant : Migration Prodinra <>
Soumis le : mercredi 3 juin 2020 - 12:28:04
Dernière modification le : lundi 21 septembre 2020 - 19:32:01

Fichier

Soft'2011 - 2011.09_1.12 - TS
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02747863, version 1
  • PRODINRA : 164645

Citation

Christian Bessière, Patrice Boizumault, Simon de Givry, Patricia Gutierrez, Samir Loudini, et al.. Decomposing global cost functions. 11th Workshop on Preferences and Soft Contraints (Soft), Labo/service de l'auteur, Ville service, Pays service., Sep 2011, Perugia, Italy. ⟨hal-02747863⟩

Partager

Métriques

Consultations de la notice

19

Téléchargements de fichiers

10