Paper Info
Title
Choosing probability distributions for stochastic local search and the role of make versus break
Abstract
Stochastic local search solvers for SAT made a large progress with the introduction of probability distributions like the ones used by the SAT Competition 2011 winners Sparrow2010 and EagleUp. These solvers though used a relatively complex decision heuristic, where probability distributions played a marginal role. In this paper we analyze a pure and simple probability distribution based solver probSAT, which is probably one of the simplest SLS solvers ever presented. We analyze different functions for the probability distribution for selecting the next flip variable with respect to the performance of the solver. Further we also analyze the role of make and break within the definition of these probability distributions and show that the general definition of the score improvement by flipping a variable, as make minus break is questionable. By empirical evaluations we show that the performance of our new algorithm exceeds that of the SAT Competition winners by orders of magnitude.
Year
DOI
Venue
2012
10.1007/978-3-642-31612-8_3
SAT
Keywords
Field
DocType
general definition,marginal role,stochastic local search solvers,next flip variable,sat competition winner,solver probsat,simple probability distribution,choosing probability distribution,simplest sls solvers,sat competition,probability distribution
Heuristic,Mathematical optimization,Random walk,Computer science,Probability distribution,Solver,Local search (optimization)
Conference
Citations 
PageRank 
References 
28
1.02
13
Authors
2
Name
Order
Citations
PageRank
Adrian Balint11316.46
Uwe Schöning2998105.69