CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem

Abstract

The k-sat problem is a prototypical constraint satisfaction problem. There are many algorithms to study k-sat problem, BP algorithm is famous one of them. But BP algorithm does not converge when $\alpha$(constraint density)is bigger than some threshold value. In this paper we use CCCP (Concave Convex Procedure) algorithm to study 3-sat problem and we get better results than BP algorithm that CCCP algorithm still converges when BP algorithm does not converge. Our work almost builds on recent results by Yuille \cite{Yuille2002} who apply the CCCP algorithm to Bethe and Kikuchi free energies and obtained two algorithms on 2D and 3D spin glasses. Our implementation of CCCP algorithm on 3-sat problem is some different from his implementation and we have some different views about CCCP algorithm's some properties. Some difference of these maybe because of CCCP algorithm have different properties and implementation process on different problem and some others of these are related to the CCCP algorithm itself. Our work indicates that CCCP algorithm has more learning and inference applications.

arXiv comment11 pages, 5 figures

References in corpus (10)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The Entropy of the K-Satisfiability Problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Supersymmetric quenched complexity in the Sherrington-Kirkpatrick model
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• First Order Phase Transition and Phase Coexistence in a Spin-Glass Model
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Partition Function Expansion on Region-Graphs and Message-Passing Equations
• Anytime Belief Propagation Using Sparse Domains