From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)

From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)

Gilles Pesant

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Journal track. Pages 5100-5104. https://doi.org/10.24963/ijcai.2020/715

The distinctive driving force of constraint programming (CP) to solve combinatorial problems has been a privileged access to problem structure through the high-level models it uses. We investigate a richer propagation medium for CP made possible by recent work on counting solutions inside constraints. Beliefs about individual variable-value assignments are exchanged between contraints and iteratively adjusted. Its advantage over standard belief propagation is that the higher-level models do not tend to create as many cycles, which are known to be problematic for convergence. We find that it significantly improves search guidance.
Keywords:
Constraints and SAT: Constraints: Modeling, Solvers, Applications
Constraints and SAT: Constraints and Data Mining ; Constraints and Machine Learning
Heuristic Search and Game Playing: Combinatorial Search and Optimisation