An Algorithm Based on Tabu Search for Satisfiability Problem

In this paper, a computationally effective algorithmbased on tabu search for solving the satisfiability problem (TSSAT) isproposed. Some novel and efficient heuristic strategies for generatingcandidate neighborhood of the current assignment and selectingvariables to be flipped are presented. Especially, the aspiration criterionand tabu list structure of TSSAT are different from those oftraditional tabu search. Computational experiments on a class ofproblem instances show that, TSSAT, in a reasonable amount of computertime, yields better results than Novelty which is currently among thefastest known. Therefore, TSSAT is feasible and effective.