Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Friday, September 30, 2016 - 3:16:04 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM
Long-term archiving on: : Saturday, December 31, 2016 - 3:47:47 PM


Files produced by the author(s)




Christian Bessière, Simon de Givry, Thomas Schiex, Thi Hông Hiêp Nguyên. Triangle-based consistencies for cost function networks
. Constraints, Springer Verlag, 2017, 22 (2), pp.230-264. ⟨10.1007/s10601-016-9250-1⟩. ⟨lirmm-01374514⟩



Record views


Files downloads