Efficient 2 and 3-Flip Neighborhood Search Algorithms
for the MAX SAT: Experimental Evaluation
Mutsunori Yagiura and Toshihide Ibaraki
For problems SAT and MAX SAT,
local search algorithms are widely acknowledged
as one of the most effective approaches.
Most of the local search algorithms are based on the 1-flip neighborhood,
which is the set of solutions obtainable by flipping
the truth assignment of one variable.
In this paper,
we consider $r$-flip neighborhoods for $r = 2, 3$,
and examine their effectiveness by computational experiments.
In the accompanying paper,
we proposed new implementations
of these neighborhoods,
and showed that
the expected size of 2-flip neighborhood is $O(n+m)$
and that of 3-flip neighborhood is $O(m+t^2n)$,
compared to their original size $O(n^2)$ and $O(n^3)$,
where $n$ is the number of variables,
$m$ is the number of clauses
and $t$ is the maximum number of appearances of one variable.
These are used in this paper
under the framework of tabu search and other metaheuristic methods,
and compared with other
existing algorithms with 1-flip neighborhood.
The results exhibit good prospects of larger neighborhoods.
weighted MAX SAT, SAT, local search, metaheuristics, neighborhood.
Journal of Heuristics, Vol. 7, pp. 423-442, 2001.
Erratum: In the following phrase in Section 4.1,
``where the cost is the weighted sum of edges having different colors
on their end vertices,'' the word `different'
should be `the same.'
Back to the Paper List