Paper Info
Title
On the relative merits of simple local search methods for the MAX-SAT problem
Abstract
Algorithms based on local search are popular for solving many optimization problems including the maximum satisfiability problem (MAX-SAT). With regard to MAX-SAT, the state of the art in performance for universal (i.e. non specialized solvers) seems to be variants of Simulated Annealing (SA) and MaxWalkSat (MWS), stochastic local search methods. Local search methods are conceptually simple, and they often provide near optimal solutions. In contrast, it is relatively rare that local search algorithms are analyzed with respect to the worst-case approximation ratios. In the first part of the paper, we build on Mastrolilli and Gambardella’s work [14] and present a worst-case analysis of tabu search for the MAX-k-SAT problem. In the second part of the paper, we examine the experimental performance of determinstic local search algorithms (oblivious and non-oblivious local search, tabu search) in comparison to stochastic methods (SA and MWS) on random 3-CNF and random k-CNF formulas and on benchmarks from MAX-SAT competitions. For random MAX-3-SAT, tabu search consistently outperforms both oblivious and non-oblivious local search, but does not match the performance of SA and MWS. Initializing with non-oblivious local search improves both the performance and the running time of tabu search. The better performance of the various methods that escape local optima in comparison to the more basic oblivious and non-oblivious local search algorithms (that stop at the first local optimum encountered) comes at a cost, namely a significant increase in complexity (which we measure in terms of variable flips). The performance results observed for the unweighted MAX-3-SAT problem carry over to the weighted version of the problem, but now the better performance of MWS is more pronounced. In contrast, as we consider MAX-k-SAT as k is increased, MWS loses its advantage. Finally, on benchmark instances, it appears that simulated annealing and tabu search initialized with non-oblivious local search outperform the other methods on most instances.
Year
DOI
Venue
2010
10.1007/978-3-642-14186-7_19
SAT
Keywords
Field
DocType
max-sat problem,tabu search,determinstic local search algorithm,simple local search method,local search method,local search algorithm,relative merit,non-oblivious local search algorithm,escape local optimum,better performance,stochastic local search method,local search,non-oblivious local search,satisfiability,simulated annealing,optimization problem
Hill climbing,Mathematical optimization,Search algorithm,Guided Local Search,Local optimum,Computer science,Algorithm,Beam search,Local search (optimization),Tabu search,Iterated local search
Conference
Volume
ISSN
ISBN
6175
0302-9743
3-642-14185-4
Citations 
PageRank 
References 
2
0.37
15
Authors
2
Name
Order
Citations
PageRank
Denis Pankratov1717.81
Allan Borodin22947658.84