Local search methods based on variable focusing for random K-satisfiability

Rémi Lemoy, Mikko Alava, and Erik Aurell
Phys. Rev. E 91, 013305 – Published 14 January 2015

Abstract

We introduce variable focused local search algorithms for satisfiabiliity problems. Usual approaches focus uniformly on unsatisfied clauses. The methods described here work by focusing on random variables in unsatisfied clauses. Variants are considered where variables are selected uniformly and randomly or by introducing a bias towards picking variables participating in several unsatistified clauses. These are studied in the case of the random 3-SAT problem, together with an alternative energy definition, the number of variables in unsatisfied constraints. The variable-based focused Metropolis search (V-FMS) is found to be quite close in performance to the standard clause-based FMS at optimal noise. At infinite noise, instead, the threshold for the linearity of solution times with instance size is improved by picking preferably variables in several UNSAT clauses. Consequences for algorithmic design are discussed.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 8 July 2014

DOI:https://doi.org/10.1103/PhysRevE.91.013305

©2015 American Physical Society

Authors & Affiliations

Rémi Lemoy1,2,*, Mikko Alava1,†, and Erik Aurell2,3,‡

  • 1Aalto University, Department of Applied Physics, Espoo, Finland
  • 2Aalto University, Department of Information and Computer Science, Espoo, Finland
  • 3Department of Computational Biology, and ACCESS Linnaeus Centre, KTH-Royal Institute of Technology, Stockholm, Sweden

  • *remilemoy@gmail.com
  • mikko.alava@aalto.fi
  • eaurell@kth.se

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 91, Iss. 1 — January 2015

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×