An algorithm based on tabu search for satisfiability problem
In this paper, a computationally effective algorithm based on tabu search for solving the satisfiability problem (TSSAT) is proposed. Some novel and efficient heuristic strategies for generating candidate neighborhood of the current assignment and selecting variables to be flipped are presented. Especially, the aspiration criterion and tabu list structure of TSSAT are different from those of traditional tabu search. Computational experiments on a class of problem instances show that, TSSAT, in a reasonable amount of computer time, yields better results than Novelty which is currently among the fastest known. Therefore, TSSAT is feasible and effective.
tabu search satisfiability local search