An Analysis on Message Passing Algorithms to Solve the Constraint Satisfaction Problems |
Constraint Satisfaction Problems (CSPs) are defined over a set ofvariables whose state must satisfy a number of constraints. We study a class ofalgorithms called Message Passing Algorithms, which aim at finding theprobability distribution of the variables over the space of satisfyingassignments. These algorithms involve passing local messages (according to somemessage update rules) over the edges of a factor graph constructedcorresponding to the CSP. We focus on the Belief Propagation (BP) algorithm,which finds exact solution marginals for tree-like factor graphs. However,convergence and exactness cannot be guaranteed for a general factor graph. Wepropose a method for improving BP to account for cycles in the factor graph. Wealso study another message passing algorithm known as Survey Propagation (SP),which is empirically quite effective in solving random KSATinstances, even when the density is close to the satiability threshold. Wecontribute to the theoretical understanding of SP by deriving the SP equationsfrom the BP message update rules.