Circumspect descent prevails in solving random constraint satisfaction problems
Edited by Giorgio Parisi, University of Rome, Rome, Italy, and approved August 22, 2008
Abstract
We study the performance of stochastic local search algorithms for random instances of the K-satisfiability (K-SAT) problem. We present a stochastic local search algorithm, ChainSAT, which moves in the energy landscape of a problem instance by never going upwards in energy. ChainSAT is a focused algorithm in the sense that it focuses on variables occurring in unsatisfied clauses. We show by extensive numerical investigations that ChainSAT and other focused algorithms solve large K-SAT instances almost surely in linear time, up to high clause-to-variable ratios α; for example, for K = 4 we observe linear-time performance well beyond the recently postulated clustering and condensation transitions in the solution space. The performance of ChainSAT is a surprise given that by design the algorithm gets trapped into the first local energy minimum it encounters, yet no such minima are encountered. We also study the geometry of the solution space as accessed by stochastic local search algorithms.
Acknowledgments.
This work was supported by the Integrated Project EVERGROW of the European Union (J.A. and S.K.), the Swedish Science Council through Linnaeus Centre ACCESS (E.A.), and the Academy of Finland (Grant 117499, to P.K.), and through the Center of Excellence Program (M.A. and S.S.). We thank the Department of Computer Science of University of Helsinki and Swedish Institute of Computer Science for the use of a little over 13 years of central processing unit time, and the Kavli Institute for Theoretical Physics China (KITPC) for hospitality.
References
1
MR Garey, DS Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
2
, eds D Du, J Gu, P Pardalos (Am Math Soc, Providence RI) Satisfiability Problem: Theory and Applicationsm, DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol 35 (1997).
3
OC Martin, R Monasson, R Zecchina, Statistical mechanics methods and phase transitions in optimization problems. Theor Comput Sci 265, 3–67 (2001).
4
, eds O Dubois, R Monasson, B Selman, R Zecchina, Special Issue on NP-Hardness and Phase Transitions. Theor Comput Sci, pp. 265 (2001).
5
D Mitchell, B Selman, H Levesque Hard and Easy Distributions of SAT Problems (AAAI Press, San Jose, CA), pp. 459–465, AAAI-92. (1992).
6
M Davis, G Logemann, DW Loveland, A machine program for theorem proving. Commun ACM 5, 394–397 (1962).
7
M Mézard, G Parisi, R Zecchina, Analytic and algorithmic solutions of random satisfiability problems. Science 297, 812–815 (2002).
8
, eds E Aarts, JK Lenstra (Wiley, New York Local Search for Combinatorial Optimization, 1997).
9
HH Hoos, T Stützle Stochastic Local Search: Foundations and Applications (Elsevier, Amsterdam, 2005).
10
B Selman, H Kautz, D McAllester Ten Challenges in Propositional Reasoning and Search (Elsevier, Amsterdam), pp. 50–54, IJCAI-97. (1997).
11
H Kautz, B Selman, The state of SAT. Discrete Appl Math 155, 1514–1524 (2007).
12
S Kirkpatrick, SD Gelatt, MP Vecchi, Optimization by simulated annealing. Science 220, 671–680 (1983).
13
CH Papadimitriou On Selecting a Satisfying Truth Assignment (IEEE Computer Society, New York), pp. 163–169, FOCS-91. (1991).
14
W Barthel, AK Hartmann, M Weigt, Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms. Phys Rev E 67, 066104. (2003).
15
G Semerjian, R Monasson, Relaxation and metastability in a local search procedure for the random satisfiability problem. Phys Rev E 67, 066103. (2003).
16
B Selman, H Kautz, B Cohen Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, eds DS Johnson, MA Trick (Am Math Soc, Providence RI) Vol 26, 521–532 (1996).
17
J Ardelius, E Aurell, Behavior of heuristics on large and hard satisfiability problems. Phys Rev E 74, 037702. (2006).
18
E Aurell, U Gordon, S Kirkpatrick Comparing Beliefs, Surveys and Random Walks (MIT Press, Boston) Vol 17, 49–56, Advances in Neural Information Processing Systems (NIPS-04). (2005).
19
S Seitz, M Alava, P Orponen, Focused local search for random 3-satisfiability. J Stat Mech Theor Exp, 06006. (2005).
20
S Mertens, M Mézard, R Zecchina, Threshold values for random K-SAT from the cavity method. Rand Struct Algorithms 28, 340–373 (2006).
21
M Mézard, T Mora, R Zecchina, Clustering of solutions in the random satisfiability problem. Phys Rev Lett 94, 197205 (2005).
22
F Krzakala, A Montanari, F Ricci-Tersenghi, G Semerjian, L Zdeborova, Gibbs states and the set of solutions of random constraint satisfaction problems. Proc Natl Acad Sci USA 104, 10318–10323 (2007).
23
D Battaglia, A Braunstein, J Chavas, R Zecchina, Source coding by efficient selection of ground-state clusters. Phys Rev E 72, 015103. (2005).
24
G Parisi, On local equilibrium equations for clustering states. Technical Report, cs.CC/0212047. Available at http://arxiv.org/abs/cs/0212047. (2002).
25
G Semerjian, On the freezing of variables in random constraint satisfaction problems. J Stat Phys 130, 251–293 (2008).
26
L Kroc, A Sabharwal, B Selman Survey Propagation Revisited (AUAI Press, Arlington, VA), pp. 217–226 (2007).
Information & Authors
Information
Published in
Classifications
Copyright
© 2008 by The National Academy of Sciences of the USA.
Submission history
Received: January 16, 2008
Published online: October 7, 2008
Published in issue: October 7, 2008
Keywords
Acknowledgments
This work was supported by the Integrated Project EVERGROW of the European Union (J.A. and S.K.), the Swedish Science Council through Linnaeus Centre ACCESS (E.A.), and the Academy of Finland (Grant 117499, to P.K.), and through the Center of Excellence Program (M.A. and S.S.). We thank the Department of Computer Science of University of Helsinki and Swedish Institute of Computer Science for the use of a little over 13 years of central processing unit time, and the Kavli Institute for Theoretical Physics China (KITPC) for hospitality.
Notes
This article is a PNAS Direct Submission.
Authors
Competing Interests
The authors declare no conflict of interest.
Metrics & Citations
Metrics
Citation statements
Altmetrics
Citations
Cite this article
Circumspect descent prevails in solving random constraint satisfaction problems, Proc. Natl. Acad. Sci. U.S.A.
105 (40) 15253-15257,
https://doi.org/10.1073/pnas.0712263105
(2008).
Copied!
Copying failed.
Export the article citation data by selecting a format from the list below and clicking Export.
Cited by
Loading...
View Options
View options
PDF format
Download this article as a PDF file
DOWNLOAD PDFLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Personal login Institutional LoginRecommend to a librarian
Recommend PNAS to a LibrarianPurchase options
Purchase this article to access the full text.