Abstract
During local search, clauses may frequently be satisfied or falsified. Modern SLS algorithms often exploit the falsifying history of clauses to select a variable to flip, together with variable properties such as score and age. The score of a variable x refers to the decrease in the number of unsatisfied clauses if x is flipped. The age of x refers to the number of steps done since the last time when x was flipped.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balint, A., Fröhlich, A.: Improving Stochastic Local Search for SAT with a New Probability Distribution. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 10–15. Springer, Heidelberg (2010)
Hoos, H.: An Adaptive Noise Mechanism for WalkSAT. In: Proceedings of AAAI 2002, pp. 655–660. AAAI Press / The MIT Press (2002)
Li, C.-M., Huang, W.Q.: Diversification and Determinism in Local Search for Satisfiability. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol. 3569, pp. 158–172. Springer, Heidelberg (2005)
Li, C.-M., Wei, W., Li, Y.: Exploiting Historical Relationships of Clauses and Variables in Local Search for Satisfiability (Poster Presentation). In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 479–480. Springer, Heidelberg (2012)
McAllester, D.A., Selman, B., Kautz, H.: Evidence for invariant in local search. In: Proceedings of AAAI 1997, pp. 321–326 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, C.M., Li, Y. (2012). Satisfying versus Falsifying in Local Search for Satisfiability. In: Cimatti, A., Sebastiani, R. (eds) Theory and Applications of Satisfiability Testing – SAT 2012. SAT 2012. Lecture Notes in Computer Science, vol 7317. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31612-8_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-31612-8_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31611-1
Online ISBN: 978-3-642-31612-8
eBook Packages: Computer ScienceComputer Science (R0)