||Efficient 2 and 3-flip
Neighbourhood Search Algorithms for MaxSAT
Yagiura and Ibaraki
Most Stochastic Local Search (SLS) algorithms
Satisfiability are based on a "1-flip neighbourhood"
- that is, each
step in the algorithm involves flipping only
one propositional variable
which is chosen according to some heuristic.
In their paper, Yagiura
and Ibaraki examine the effects of using larger
neighbourhoods on the
performance of various algorithms for MaxSAT.
I will describe their
algorithm and the techniques which they use for
implementation, and then briefly contrast this
with some of the research
that has been going on in the Beta Lab on MaxSAT.