Yagiura, M.; Ibaraki, T. Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation. (English) Zbl 1041.68091 J. Heuristics 7, No. 5, 423-442 (2001). 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. Cited in 9 Documents 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 Keywords:weighted MAX SAT; SAT; local search; metaheuristics; neighborhood Software:Walksat PDFBibTeX XMLCite \textit{M. Yagiura} and \textit{T. Ibaraki}, J. Heuristics 7, No. 5, 423--442 (2001; Zbl 1041.68091) Full Text: DOI