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.
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)
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
Return to my home page.