Triangle-based consistencies for cost function networks
详细信息 查看全文
- 作者：Hiep Nguyen ; Christian Bessiere ; Simon de Givry ; Thomas Schiex
- 关键词：Cost function networks ; Weighted CSP ; Constraint optimization problems ; High order consistencies ; Restricted path consistency ; Path inverse consistency ; Max ; restricted path consistency
- 刊名：Constraints
- 出版年：2017
- 出版时间：April 2017
- 年：2017
- 卷：22
- 期：2
- 页码：230-264
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence (incl. Robotics); Optimization; Computing Methodologies; Operation Research/Decision Theory;
- 出版者：Springer US
- ISSN：1572-9354
- 卷排序：22
文摘
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.