IJCAI 2020poster0 citations
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.
Constraints and SAT: Constraints: Modeling, Solvers, ApplicationsConstraints and SAT: Constraints and Data MiningConstraints and Machine LearningHeuristic Search and Game Playing: Combinatorial Search and Optimisation
BibTeX
@inproceedings{ijcai2020p715,
title = {From Support Propagation to Belief Propagation in Constraint Programming (Extended Abstract)},
author = {Pesant, Gilles},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {5100--5104},
year = {2020},
month = {7},
note = {Journal track},
doi = {10.24963/ijcai.2020/715},
url = {https://doi.org/10.24963/ijcai.2020/715},
}