Circumspect descent prevails in solving random constraint satisfaction problems

Edited by Giorgio Parisi, University of Rome, Rome, Italy, and approved August 22, 2008
October 7, 2008
105 (40) 15253-15257

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.

Continue Reading

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

The cover image for PNAS Vol.105; No.40
Proceedings of the National Academy of Sciences
Vol. 105 | No. 40
October 7, 2008
PubMed: 18832149

Classifications

Submission history

Received: January 16, 2008
Published online: October 7, 2008
Published in issue: October 7, 2008

Keywords

  1. geometry of solutions
  2. local search
  3. performance
  4. random K-SAT

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

Affiliations

Mikko Alava
Department of Engineering Physics, Helsinki University of Technology, P.O. Box 1100, FI-02015, Espoo, Finland;
John Ardelius
Swedish Institute of Computer Science AB, SE-164 29 Kista, Sweden;
Department of Computational Biology, AlbaNova University Centre, SE-106 91 Stockholm, Sweden;
Department of Computational Biology, AlbaNova University Centre, SE-106 91 Stockholm, Sweden;
Linnaeus Centre, KTH-Royal Institute of Technology, SE-100 44 Stockholm, Sweden;
Petteri Kaski
Helsinki Institute for Information Technology (HIIT), Department of Computer Science, University of Helsinki, P.O.Box 68, FI-00014, Helsinki, Finland;
Supriya Krishnamurthy
Swedish Institute of Computer Science AB, SE-164 29 Kista, Sweden;
School of Information and Communication Technology, KTH-Royal Institute of Technology, SE-164 40 Kista, Sweden; and
Pekka Orponen
Department of Information and Computer Science, Helsinki University of Technology, P.O. Box 5400, FI-02015, Espoo, Finland
Sakari Seitz
Department of Engineering Physics, Helsinki University of Technology, P.O. Box 1100, FI-02015, Espoo, Finland;
Department of Information and Computer Science, Helsinki University of Technology, P.O. Box 5400, FI-02015, Espoo, Finland

Notes

To whom correspondence should be addressed. E-mail: [email protected]
Author contributions: M.A. and E.A. designed research; M.A., J.A., E.A., P.K., and S.S. performed research; S.S. contributed new reagents/analytic tools; M.A., E.A., P.K., S.K., and S.S. analyzed data; and M.A., E.A., P.K., and P.O. wrote the paper.

Competing Interests

The authors declare no conflict of interest.

Metrics & Citations

Metrics

Note: The article usage is presented with a three- to four-day delay and will update daily once available. Due to ths delay, usage data will not appear immediately following publication. Citation information is sourced from Crossref Cited-by service.


Citation statements

Altmetrics

Citations

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 PDF

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Personal login Institutional Login

    Recommend to a librarian

    Recommend PNAS to a Librarian

    Purchase options

    Purchase this article to access the full text.

    Single Article Purchase

    Circumspect descent prevails in solving random constraint satisfaction problems
    Proceedings of the National Academy of Sciences
    • Vol. 105
    • No. 40
    • pp. 15221-15634

    Figures

    Tables

    Media

    Share

    Share

    Share article link

    Share on social media