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 curred assignment and selecting varibables to be flipped are presented. Especially,the aspiration criterion and tabu list tructure of TSSAT are different from those of traditional tabu search.Computational experiments on a class of problem insteances 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.

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. This work was supported by the NKBRSF of China (G1998030600). HUANG Wenqi is a professor and Ph.D. supervisor of the Huazhong University of Science and Technology. His current research interests include solving NP hard problems by quasiphysics and personification method. ZHANG Defu received his B.S. degree in computational mathematics in 1996, and his M.S. degree in computational mathematics in 1999, both from Xiangtan University. He is currently a Ph.D. candidate in the School of Computer Science at Huazhong University of Science and Technology. His current research interests lie in empirical algorithms, artificial intelligence and combinatorial optimization. WANG Houxiang is an associate professor and a Ph.D. candidate in the School of Computer Science at Huazhong University of Science and Technology. His current research interests lie in network, multi-media, algorithm design.