A Probabilistic-Based Model for Binary CSP
This work provides a theoretical framework for CSP analysis, but it appears incremental as it builds on existing CSP methods without clear broad application impact.
The paper tackles the problem of analyzing binary constraint satisfaction problems (CSPs) by introducing a probabilistic model that predicts domain inconsistencies, resulting in expressions for probabilities and expectations of arc-inconsistent values, along with bounds and a polynomial-time algorithm for propagation.
This work introduces a probabilistic-based model for binary CSP that provides a fine grained analysis of its internal structure. Assuming that a domain modification could occur in the CSP, it shows how to express, in a predictive way, the probability that a domain value becomes inconsistent, then it express the expectation of the number of arc-inconsistent values in each domain of the constraint network. Thus, it express the expectation of the number of arc-inconsistent values for the whole constraint network. Next, it provides bounds for each of these three probabilistic indicators. Finally, a polytime algorithm, which propagates the probabilistic information, is presented.