Warning Propagation Algorithm for the MAX-3-SAT Problem
Xiaofeng Wang, Jiulei Jiang · IEEE Transactions on Emerging Topics in Computing · 2017
Message propagation algorithms are widely used in approximate inference e.g. Cyber-Social Data Processing and Intelligence Mining. Especially, these algorithms enable hard region become narrower and thus they are very effective in solving satisfiability problems. Warning Propagation algorithm is one kind of basic message propagation algorithms. Based on this Warning Propagation algorithm, we designed a WPY algorithm to solve the MAX-3-SAT problem. We obtained a set of stable warning information, and the value of the partial variable is decided by using the stable set with high probability. Finally, the experiment results show that the WPY algorithm can effectively solve the random MAX-3-SAT instances.