Codes for generalized message passing algorithms for various constraint satisfaction and optimization problems.
 
 
 
 
Survey Propagation and Belief Propagation based algorithms for random satisfiability
 

Random K-SAT code: This is an implementation of a message-passing algorithm (SP) designed to work for large random K-SAT formulas close to their SAT/UNSAT threshold ( M/N = 4.267, 9.931,21.117,43.37,... for K=3,4,5,6,... resp. See: http://arxiv.org/abs/cs.CC/0309020). Although we consider that it may be possible to generalize SP in many ways (e.g. adding backtracking, adding corrections for correlations, using SP as a source for some randomized search, etc), the distributed implementation was not designed with this in mind. We have tried to keep the algorithm simple for us and others to understand. This implementation is simply a proof-of-concept for random SAT. There is a parameter in the code which allows to interpolate between SP and BP, two message-passing algorithmis which compute sightly different marginals from the set of solutions. That said, in order to use the algorithm on different problems, some modifications need to be implemented, like taking explicit care of correlations arising from locally interconnected groups of constraints. Such structures are often artificially introduced by reductions of the problems onto SAT. We should mention that the algorithmic strategy can be directly implemented on decision problems without going through the SAT reduction, as it has been done for graph coloring.
 

Code: SP for random K-SAT. The help gives options for running different types of SP.

Download:   sp-1.4b.tgz

Older versions:   sp-1.3.tgz, sp-1.2.tgz, sp-1.1.tgz

Companion paper:    Survey propagation: an algorithm for satisfiability  A. Braunstein, M. Mezard, R. Zecchina, Random Structures and Algorithms 27, 201-226 (2005)
 

Code: SP-Y for the random max-3-sat problem

Download :   spy-1.2.tar.gz

Companion paper:    Minimizing energy below the glass thresholds  D. Battaglia, M. Kolar, R. Zecchina, Phys. Rev. E 70, 036107 (2004)


Message-passing + reinforcement: instead of decimation one may use a fully distributed (local) strategy to find solutions of constraint satisfaction problems. This strategy works very well on both classical problems (K-sat, Q-col,...) as well as on qualitatively new examples which are found in optimization problems over dense networks of constraints. Here you may find the code of a new learning algorithm for neural networks with discrete synapses, a problem which was considered difficult to solve also in the case of random patterns. The code can be generalized to deal with arbitrary neural network topologies.
 

Code for the binary perceptron

Download :   Bperc.tgz

Companion paper:    Learning by message-passing in networks of discrete synapses  A. Braunstein, R. Zecchina, Phys. Rev. Lett.96, 030201 (2006)

An older paper on local reinforcement:    Survey-propagation decimation through distributed local computations  J. Chavas, C. Furtlehner, M. Mezard, R. Zecchina, J. Stat. Mech. P11016 (2005)
 
Message-passing + global constraints: Some types of global constraints (like topological connectivity of a graph) can be appropriately mapped into sets of local constraints and analyzed with BP. Here we provide preliminary version of an implementation of BP for the minimum weight steiner problem: find a connected subgraph of minimum weight containing a predefined subset of vertices.

Code: BP for the steiner tree problem

Download :   bpsteiner.tgz


 
 
 

Other related publications

Return to my home page.