From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)
Abstract
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.
Cite
Text
Pesant. "From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/715Markdown
[Pesant. "From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/pesant2020ijcai-support/) doi:10.24963/IJCAI.2020/715BibTeX
@inproceedings{pesant2020ijcai-support,
title = {{From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)}},
author = {Pesant, Gilles},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {5100-5104},
doi = {10.24963/IJCAI.2020/715},
url = {https://mlanthology.org/ijcai/2020/pesant2020ijcai-support/}
}