Analyses on the 2 and 3-Flip Neighborhoods for the MAX SAT

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 \geq 2$, and propose, for $r=2, 3$, new implementations that reduce the number of candidates in the neighborhood without sacrificing the solution quality. For 2-flip (resp., 3-flip) neighborhood, we show that its expected size is $O(n+m)$ (resp., $O(m+t^2n)$), which is usually much smaller than the original size $O(n^2)$ (resp., $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. Computational results tell that these estimates by the expectation well represent the real performance.

Key Words: MAX SAT, SAT, local search, neighborhood

Journal of Combinatorial Optimization, Vol. 3, No. 1, pp. 95-114, July 1999.

PS file


Back to the Paper List