TL;DR
This paper introduces a novel approach to constraint programming (CP) by adapting belief propagation (BP), a technique from probabilistic inference, to CP's problem-solving framework. By exchanging "beliefs" about variable assignments between constraints, this method significantly enhances search guidance, leading to more efficient problem-solving, especially for complex combinatorial problems.
What Problem Does This Paper Address?
Constraint Programming (CP) excels at solving combinatorial problems by leveraging high-level models and powerful inference algorithms. A core mechanism in CP is "constraint propagation," which prunes variable domains by removing values that cannot satisfy a constraint. While effective and guaranteed to converge, standard CP propagation offers a rather "flat" form of information exchange: values are either supported or not. This paper addresses the limitation of this binary information by proposing a richer propagation medium. It aims to integrate the more nuanced probabilistic reasoning of Belief Propagation (BP), which exchanges detailed "beliefs" (probabilities) about variable assignments, into the CP framework. This richer information exchange is expected to provide better guidance for the search process, especially in complex problems where standard propagation might not prune enough.
Methods
The paper proposes adapting Belief Propagation (BP) to Constraint Programming. Instead of simply deleting unsupported values, constraints and variables exchange "beliefs," which are essentially probability distributions over variable assignments. These beliefs are iteratively adjusted. The key innovation lies in using weighted model counting techniques to compute these beliefs for various CP constraints, including "table," "sum," "regular," "among," and "alldifferent."
- Belief Exchange: Variables and constraints communicate by sending and receiving messages representing probability distributions (beliefs) over variable assignments.
- Weighted Model Counting: To compute these beliefs, the paper leverages weighted model counting, which extends traditional counting to account for varying probabilities of assignments. This is crucial because not all solutions are equally likely.
- Constraint-Specific Counting: Efficient weighted counting algorithms are developed for different constraint types. For "alldifferent" constraints, this involves computing the permanent of a matrix derived from variable beliefs, using exact methods for small matrices and approximations for larger ones.
- Integration with CP Solver: The proposed method is integrated into a CP solver (MiniCP), where belief propagation is performed at each node of the search tree to guide branching decisions.
Datasets
The paper evaluates its approach on three combinatorial problems from the XCSP3 repository: Primes, Magic Square, and Latin Square. These are standard benchmarks for constraint satisfaction problems. No new datasets were introduced.
Key Insights and Ideas
- Richer Information for Search: The core idea is that by exchanging probabilistic beliefs rather than just binary support/unsupport information, CP can achieve significantly better search guidance. This is analogous to how BP works in probabilistic graphical models.
- Leveraging High-Level Models: The paper argues that CP's high-level, often large-arity global constraints, are well-suited for this BP-like approach. These models tend to create fewer cycles in the constraint graph compared to models decomposed into many small constraints, which is beneficial for BP's convergence properties.
- Weighted Counting as the Engine: The ability to perform weighted model counting for various constraints is the technical enabler for this richer propagation. It allows for the computation of nuanced beliefs that reflect the underlying solution distribution.
- Alldifferent Constraint Challenge: The "alldifferent" constraint poses a significant challenge due to its connection to computing permanents, a #P-complete problem. The paper proposes a practical approach using exact and approximate methods.
Key Results
- Improved Search Guidance: The proposed "max-strength" branching heuristic, guided by the CP-adapted BP, significantly outperforms the standard "minimum domain size" heuristic on the tested problems.
- Reduced Fails: For the Primes instances, the approach with 10 BP iterations solved 26 out of 32 instances backtrack-free, compared to only 4 for the baseline.
- Competitive Performance: While the computational cost of exact weighted counting can be high, especially for problems with many sum constraints, the BP-guided search often solves more instances within the time limit.
- Impact of Decomposition: Replacing a global "alldifferent" constraint with its decomposition into smaller disequality constraints led to significantly worse performance, highlighting the advantage of working with high-level constraints.
Limitations and Future Work
- Exact Weighted Counting Intractability: The paper acknowledges that exact weighted counting can be intractable for many constraints. The proposed solution for "alldifferent" uses approximations, which might limit the accuracy of beliefs in some cases.
- Convergence Guarantees: While the paper suggests that high-level CP models might reduce cycles problematic for BP convergence, it doesn't provide formal convergence guarantees for all cases.
- Future Work: The authors suggest further research into developing efficient weighted counting algorithms for more constraint families and exploring the theoretical properties of this CP-adapted BP, particularly regarding convergence. They also mention the availability of a publicly implemented prototype for further research.
Summary updated