Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT: Experimental Evaluation

Mutsunori Yagiura and Toshihide Ibaraki

Abstract:
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)$, respectively, 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.

Key Words: weighted MAX SAT, SAT, local search, metaheuristics, neighborhood.

Journal of Heuristics, Vol. 7, pp. 423-442, 2001.

PS file

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