Walksat
GSAT and WalkSat are local search algorithms to solve Boolean satisfiability problems. Both algorithms work on formulae that are in, or have been converted into, conjunctive normal form. They start by assigning a random value to each variable. If the assignment satisfies all clauses, the algorithm terminates, returning the assignment. Otherwise, a variable is flipped and the above is then repeated until all the clauses are satisfied. WalkSAT and GSAT differ in the methods used to select which variable to flip. GSAT makes the change which minimizes the number of unsatisfied clauses in the new assignment, or with some probability picks a variable at random. WalkSAT first picks a clause which is unsatisfied by the current assignment, then flips a variable within that clause. The clause is generally picked at random among unsatisfied clauses. The variable is generally picked that will result in the fewest previously satisfied clauses becoming unsatisfied, with some probability of picking one of the variables at random. When picking at random, WalkSAT is guaranteed at least a chance of one out of the number of variables in the clause of fixing a currently incorrect assignment. When picking a guessed to be optimal variable, WalkSAT has to do less calculation than GSAT because it’s considering fewer possibilities.
(Source: http://en.wikipedia.org/wiki/WalkSAT)
Keywords for this software
References in zbMATH (referenced in 209 articles )
Showing results 1 to 20 of 209.
Sorted by year (- Berend, Daniel; Twitto, Yochai: Probabilistic characterization of random Max (r)-Sat (2021)
- Kyrillidis, Anastasios; Shrivastava, Anshumali; Vardi, Moshe Y.; Zhang, Zhiwei: Solving hybrid Boolean constraints in continuous space via multilinear Fourier expansions (2021)
- Bian, Zhengbing; Chudak, Fabian; Macready, William; Roy, Aidan; Sebastiani, Roberto; Varotti, Stefano: Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results (2020)
- Ibrahim, Mohamed-Hamza; Pal, Christopher; Pesant, Gilles: Leveraging cluster backbones for improving MAP inference in statistical relational models (2020)
- Zhu, Zheng; Fang, Chao; Katzgraber, Helmut G.: (\boldsymbolborealis) -- a generalized global update algorithm for Boolean optimization problems (2020)
- Achlioptas, Dimitris; Iliopoulos, Fotis; Kolmogorov, Vladimir: A local lemma for focused stochastic algorithms (2019)
- Demaine, Erik D.; Fekete, Sándor P.; Keldenich, Phillip; Meijer, Henk; Scheffer, Christian: Coordinated motion planning: reconfiguring a swarm of labeled robots with bounded stretch (2019)
- Bernardini, Sara; Fagnani, Fabio; Smith, David E.: Extracting mutual exclusion invariants from lifted temporal planning domains (2018)
- Gnad, Daniel; Hoffmann, Jörg: Star-topology decoupled state space search (2018)
- Marques-Silva, Joao; Malik, Sharad: Propositional SAT solving (2018)
- Zhang, Yueling; Zhang, Min; Pu, Geguang; Song, Fu; Li, Jianwen: Towards backbone computing: a greedy-whitening based approach (2018)
- Fotakis, Dimitris; Kaporis, Alexis C.; Lianeas, Thanasis; Spirakis, Paul G.: Resolving Braess’s paradox in random networks (2017)
- Hutter, Frank; Lindauer, Marius; Balint, Adrian; Bayless, Sam; Hoos, Holger; Leyton-Brown, Kevin: The configurable SAT solver challenge (CSSC) (2017)
- Karapetyan, Daniel; Punnen, Abraham P.; Parkes, Andrew J.: Markov chain methods for the bipartite Boolean quadratic programming problem (2017)
- Paes, Aline; Zaverucha, Gerson; Santos Costa, Vítor: On the use of stochastic local search techniques to revise first-order logic theories from examples (2017)
- Steinmetz, Marcel; Hoffmann, Jörg: State space search nogood learning: online refinement of critical-path dead-end detectors in planning (2017)
- Surynek, Pavel: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems (2017)
- Wang, Jinyan; Yin, Minghao; Wu, Jingli: Two approximate algorithms for model counting (2017)
- Berend, Daniel; Twitto, Yochai: The normalized autocorrelation length of random Max (r)-Sat converges in probability to ((1-1/2^r)/r) (2016)
- Bischl, Bernd; Kerschke, Pascal; Kotthoff, Lars; Lindauer, Marius; Malitsky, Yuri; Fréchette, Alexandre; Hoos, Holger; Hutter, Frank; Leyton-Brown, Kevin; Tierney, Kevin; Vanschoren, Joaquin: ASlib: a benchmark library for algorithm selection (2016)