ISSN:
1573-2886
Keywords:
MAX SAT
;
SAT
;
local search
;
neighborhood
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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, 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 + t2n)), which is usually much smaller than the original size O(n2) (resp., O(n3)), 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009873324187
Permalink
