The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algorithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algorithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the multilevel tabu search against its single level variant are presented.
R. J. Wallace and E. C. Freuder, “Comparative Study of Constraint Satisfaction and Davisputnam Algorithms for Maximum Satisfiability Problems,” In: D. Johnson and M. Trick, Eds., Cliques, Coloring, and Satisfiability, 1996, pp. 587-615.
C. M. Li, W. Wei and H. Zhang, “Combining Adaptive Noise and Look-Ahead in Local Search for SAT,” Proceedings of the Tenth International Conference on Theory and Applications of Satisfiability Testing(SAT-07), volume 4501 of Lecture Notes in Computer Science, 2007, pp. 121-133.
A. R. KhudaBukhsh, L. Xu, H. H. Hoos and K. Leyton-Brown, “SATenstein: Automatically Building Local Search SAT Solvers from Components,” Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-09), 2009.
S. T. Barnard and H. D. Simon, “A Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems,” Concurrency: Practice and Experience, Vol. 6, No. 2, 1994, pp. 101-117.
G. Karypis and V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs,” SIAM Journal on Scientific Computing, Vol. 20, No. 1, 1998, pp. 359-392. doi:10.1137/S1064827595287997
D. Rodney, A. Soper and C. Walshaw, “The Application of Multilevel Refinement to the Vehicle Routing Problem,” In: D. Fogel, et al., Eds., IEEE Symposium on Computational Intelligence in Scheduling, 2007, pp. 212-219.