×

Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation. (English) Zbl 1041.68091

Summary: 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. 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.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory

Software:

Walksat
PDFBibTeX XMLCite
Full Text: DOI