Triangle-based consistencies for cost function networks


Abstract : Cost Function Networks (aka Weighted CSP) allow to model a variety of problems, such as optimization of deterministic and stochastic graphical models including Markov random Fields and Bayesian Networks. Solving cost function networks is thus an important problem for deterministic and probabilistic reasoning. This paper focuses on local consistencies which define essential tools to simplify Cost Function Networks, and provide lower bounds on their optimal solution cost. To strengthen arc consistency bounds, we follow the idea of triangle-based domain consistencies for hard constraint networks (path inverse consistency, restricted or max-restricted path consistencies), describe their systematic extension to cost function networks, study their relative strengths, define enforcing algorithms, and experiment with them on a large set of benchmark problems. On some of these problems, our improved lower bounds seem necessary to solve them.
Type de document :
Article dans une revue
Constraints, Springer Verlag, 2016, 〈10.1007/s10601-016-9250-1〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01374514
Contributeur : Joël Quinqueton <>
Soumis le : vendredi 30 septembre 2016 - 15:16:04
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : samedi 31 décembre 2016 - 15:47:47

Fichier

Hiep2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Hiep Nguyen, Christian Bessière, Simon De Givry, Thomas Schiex. Triangle-based consistencies for cost function networks
. Constraints, Springer Verlag, 2016, 〈10.1007/s10601-016-9250-1〉. 〈lirmm-01374514〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

20