Computer Science – Artificial Intelligence
Scientific paper
2009-10-07
EPTCS 5, 2009, pp. 41-53
Computer Science
Artificial Intelligence
Scientific paper
10.4204/EPTCS.5.4
Stochastic local search (SLS) has been an active field of research in the last few years, with new techniques and procedures being developed at an astonishing rate. SLS has been traditionally associated with satisfiability solving, that is, finding a solution for a given problem instance, as its intrinsic nature does not address unsatisfiable problems. Unsatisfiable instances were therefore commonly solved using backtrack search solvers. For this reason, in the late 90s Selman, Kautz and McAllester proposed a challenge to use local search instead to prove unsatisfiability. More recently, two SLS solvers - Ranger and Gunsat - have been developed, which are able to prove unsatisfiability albeit being SLS solvers. In this paper, we first compare Ranger with Gunsat and then propose to improve Ranger performance using some of Gunsat's techniques, namely unit propagation look-ahead and extended resolution.
Lynce Inês
Pereira David
Prestwich Steven
No associations
LandOfFree
On Improving Local Search for Unsatisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Improving Local Search for Unsatisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Improving Local Search for Unsatisfiability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-36143