Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

More efficient two-mode stochastic local search for random 3-satisfiability

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Stochastic local search (SLS) is a popular paradigm in incomplete solving for the Boolean satisfiability problem (SAT). Most SLS solvers for SAT switch between two modes, i.e., the greedy (intensification) mode and the diversification mode. However, the performance of these two-mode SLS algorithms lags far behind on solving random 3-satisfiability (3-SAT) problem, which is a significant special case of the SAT problem. In this paper, we propose a new hybrid scoring function called M C based on a linear combination of a greedy property m a k e and a diversification property C o n f T i m e s, and then utilize M C to develop a new two-mode SLS solver called CCMC. To evaluate the performance of CCMC, we conduct extensive experiments to compare CCMC with five state-of-the-art two-mode SLS solvers (i.e., Sparrow2011, Sattime2011, EagleUP, gNovelty+PCL and CCASat) on a broad range of random 3-SAT instances, including all large 3-SAT ones from SAT Competition 2009 and SAT Competition 2011 as well as 200 generated satisfiable huge random 3-SAT ones. The experiments illustrate that CCMC obviously outperforms its competitors, indicating the effectiveness of CCMC. We also analyze the effectiveness of the underlying ideas in CCMC and further improve the performance of CCMC on solving random 5-SAT instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. http://www.satcompetition.org

  2. http://www.cril.univ-artois.fr/SAT09/bench/random.7z

  3. http://www.cril.univ-artois.fr/SAT09/bench/random-additional.7z

  4. http://www.cril.univ-artois.fr/SAT11/bench/SAT11-Competition-SelectedBenchmarks.tar

  5. http://www.cril.univ-artois.fr/SAT11/solvers/SAT2011-sources.tar.gz

  6. http://shaoweicai.net/Code/CCASat-Opensource.zip

References

  1. Abuhamdah A, Ayob M, Kendall G, Sabar NR (2014) Population based local search for university course timetabling problems. Appl Intell 40(1):44–53

    Article  Google Scholar 

  2. Achlioptas D (2009) Random satisfiability. In: Handbook of Satisfiability, pp. 245–270

  3. Aloul FA, Sakallah KA, Markov IL (2006) Efficient symmetry breaking for Boolean satisfiability. IEEE Trans Computers 55(5):549–558

    Article  Google Scholar 

  4. Aurell E, Gordon U, Kirkpatrick S (2005) Comparing beliefs, surveys and random walks. In: Advances in Neural Information Processing Systems 17, pp. 49–56

  5. Balint A., Fröhlich A. (2010) Improving stochastic local search for SAT with a new probability distribution. In: Proceedings of SAT 2010, pp. 10–15

  6. Cai S., Su K. (2011) Local search with configuration checking for SAT. In: Proceedings of ICTAI 2011, pp. 59–66

  7. Cai S, Su K (2013) Local search for Boolean satisfiability with configuration checking and subscore. Artif Intell 204:75–98

    Article  Google Scholar 

  8. Cai S, Su K, Chen Q (2010) EWLS: a new local search for minimum vertex cover. In: Proceedings of AAAI 2010, pp. 45–50

  9. Cai S, Su K, Luo C (2013) Improving WalkSAT for random k-satisfiability problem with k > 3. In: Proceedings of AAAI 2013, pp. 145–151

  10. Cai S, Su K, Sattar A (2011) Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif Intell 175(9–10):1672–1696

    Article  MathSciNet  MATH  Google Scholar 

  11. Davis M, Logemann G, Loveland DW (1962) A machine program for theorem-proving. Commun ACM 5(7):394–397

    Article  MathSciNet  MATH  Google Scholar 

  12. Davis M, Putnam H (1960) A computing procedure for quantification theory. J ACM 7(3):201–215

    Article  MathSciNet  MATH  Google Scholar 

  13. Gableske O, Heule M (2011) EagleUP: solving random 3-SAT using SLS with unit propagation. In: Proceedings of SAT 2011, pp. 367–368

  14. Gent IP, Walsh T (1993) Towards an understanding of hill-climbing procedures for SAT. In: Proceedings of AAAI 1993, pp. 28–33

  15. Glover F (1989) Tabu search - part I. INFORMS J Comput 1(3):190–206

    Article  MATH  Google Scholar 

  16. Glover F (1990) Tabu search - part II. INFORMS J Comput 2(1):4–32

    Article  MATH  Google Scholar 

  17. Gu J (1993) Local search for satisfiability (SAT) problem. IEEE Trans Syst Man Cybern 23(4):1108–1129

    Article  Google Scholar 

  18. Hoos HH, Stützle T (2004) Stochastic local search: foundations & applications. Elsevier / Morgan Kaufmann

  19. Hutter F, Tompkins DAD, Hoos HH (2002) Scaling and probabilistic smoothing: efficient dynamic local search for SAT. In: Proceedings of CP 2002, pp. 233–248

  20. Kirkpatrick S, Selman B (1994) Critical behavior in the satisfiability of random Boolean expressions. Science 264:1297–1301

    Article  MathSciNet  MATH  Google Scholar 

  21. Li CM, Huang WQ (2005) Diversification and determinism in local search for satisfiability. In: Proceedings of SAT 2005, pp. 158–172

  22. Li CM, Li Y (2012) Satisfying versus falsifying in local search for satisfiability. In: Proceedings of SAT 2012, pp. 477–478

  23. Li CM, Wei W, Zhang H (2007) Combining adaptive noise and look-ahead in local search for SAT. In: Proceedings of SAT 2007, pp. 121–133

  24. Luo C, Su K, Cai S (2012) Improving local search for random 3-SAT using quantitative configuration checking. In: Proceedings of ECAI 2012, pp. 570–575

  25. Luong TV, Melab N, Talbi EG (2013) GPU computing for parallel local search metaheuristic algorithms. IEEE Trans Comput 62(1):173–185

    Article  MathSciNet  Google Scholar 

  26. bachir Menai ME, Batouche M (2006) An effective heuristic algorithm for the maximum satisfiability problem. Appl Intell 24(3):227–239

    Article  Google Scholar 

  27. Michiels W, Aarts EHL, Korst JHM (2007) Theoretical aspects of local search. Springer

  28. Pham DN, Duong TT, Sattar A (2012) Trap avoidance in local search using pseudo-conflict learning. In: AAAI, pp. 542–548

  29. Pham DN, Thornton J, Gretton C, Sattar A (2008) Combining adaptive and dynamic local search for satisfiability. JSAT 4(2–4):149–172

    MATH  Google Scholar 

  30. Selman B, Levesque HJ, Mitchell DG (1992) A new method for solving hard satisfiability problems. In: Proceedings of AAAI 1992, pp. 440–446

  31. da Silva FJM, Sánchez-Pérez JM, Pulido JAG, Vega-Rodríguez MA (2010) AlineaGA - a genetic algorithm with local search optimization for multiple sequence alignment. Appl Intell 32(2):164–172

    Article  Google Scholar 

  32. Thornton J, Pham DN, Bain S, Ferreira Jr. V (2004) Additive versus multiplicative clause weighting for SAT. In: Proceedings of AAAI 2004, pp. 191–196

  33. Xu L, Hoos HH, Leyton-Brown K (2012) Predicting satisfiability at the phase transition. In: Proceedings of AAAI 2012, pp. 584–590

  34. Yin L, He F, Hung WNN, Song X, Gu M (2012) Maxterm covering for satisfiability. IEEE Trans Comput 61(3):420–426

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is in part supported by 973 Program 2010CB328103, ARC Future Fellowship FT0991785, National Natural Science Foundation of China (61073033, 61003056 and 60903054), and Fundamental Research Funds for the Central Universities of China (21612414).

Author information

Authors and Affiliations

  1. Key Laboratory of High Confidence Software Technologies of Ministry of Education, Peking University, Beijing, China

    Chuan Luo

  2. Institute for Integrated and Intelligent Systems, Griffith University, Brisbane, Australia

    Kaile Su

  3. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China

    Shaowei Cai

  4. Queensland Research Laboratory, NICTA, Brisbane, Australia

    Shaowei Cai

Authors
  1. Chuan Luo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kaile Su
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shaowei Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chuan Luo.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Luo, C., Su, K. & Cai, S. More efficient two-mode stochastic local search for random 3-satisfiability. Appl Intell 41, 665–680 (2014). https://doi.org/10.1007/s10489-014-0556-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-014-0556-7

Keywords

Search

Navigation