Paper Info
Title
Constraint Satisfaction by Survey Propagation
Abstract
Survey Propagation (SP) is an algorithm designed for solving typical instances of random con- straint satisfiability problems. It has been successfully tested on random 3-satisfiability (3-sat) and random G(n, c n) graph 3-coloring (3-col), in the hard region of the parameter space, relatively close the the SAT/UNSAT phase transition. Here we provide a generic formalism which applies to a wide class of discrete Constraint Satisfaction Problems. In this paper we suggest a new theoretical framework for the so called "Survey Propagation" (SP) equations that are at the root of both the analysis and the algorithms used in ref. (1, 2, 3, 4) to solve the random 3-Sat and q-Coloring problems. In the more general context of constraint satisfaction problems we propose a slightly different way of deriving the equations which we hope can shed some light on the potentialities of the algorithms and which makes clear the differences with other well known iterative probabilistic algorithms. This line of approach, also discussed in (5) for the satisfiability problem, is developed here systematically through the addition of an extra state for the variables which allows to take care of the clustered structure of the space of solutions. Within clusters a variable can be either "frozen" to some value - that is, the variable takes always the same value for all solutions (satisfying assignments) within the cluster - or it may be "unfrozen" - that is it fluctuates from solution to solution within the cluster. As we shall discuss, scope of the SP equations is to properly describe the cluster to cluster fluctuations by associating to unfrozen variables an extra state to be added to those belonging to the original definition of the problem. The overall algorithmic strategy is iterative and decomposable in two elementary steps: First, the marginal probabilities of frozen variables are evaluated by the SP message-passing procedure; Second - the so called decimation step - using such information some variables are fixed and the problem is simplified. While the first step is unavoidable if one is interested in marginal probabilities, the second step is just dictated by simplicity and we expect that there could exist other ways of efficiently using the information provided by the marginals. Throughout the paper, a detailed comparison with a similar message-passing procedure, Belief Propagation, which does not make assumptions about the structure of the solution space will also be given. The structure of the paper is as follows. In Sec. II, we provide the general formalism, namely the definitions of Constraint Satisfaction Problems, Factor Graphs and Cavities, with concrete reference to the cases of Coloring and Satisfiability. In Sec. III, we introduce the warnings and the local fields whose histograms will provide the so called Belief Propagation equations. Finally in Sec. IV, clusters are introduced and the SP equations are derived. Explicit equations are given for both 3-col and 3-sat and the decimation procedure is discussed.
Year
Venue
Keywords
2002
Clinical Orthopaedics and Related Research
constraint satisfaction,probabilistic algorithm,phase transition,parameter space,satisfiability,factor graph,neural network,message passing,col,constraint satisfaction problem,computational complexity,belief propagation,algorithm design,local field
Field
DocType
Volume
Discrete mathematics,Constraint satisfaction,Combinatorics,Local consistency,Constraint graph,Constraint satisfaction problem,Complexity of constraint satisfaction,Parameter space,Constraint logic programming,Mathematics,Hybrid algorithm (constraint satisfaction)
Journal
cond-mat/0
ISSN
Citations 
PageRank 
Advances in Neural Information Processing Systems. Vol 9. Oxford University Press; 2005. 424
22
2.96
References 
Authors
0
4
Name
Order
Citations
PageRank
Alfredo Braunstein147938.97
Marc Mézard259039.09
Martin Weigt3222.96
riccardo zecchina463755.46