Solving weighted Max-Sat optimization problems using a Taboo Scatter Search metaheuristic

ABSTRACT

In the last three decades, many researchers have focused on the Satisfiability problem and on many of its variants, in particular, on the Weighted Maximum Satisfiability problem (Max-W-Sat). The latter is known to be difficult to solve, due to a high number of local minima present in its search space. In this Work, we present a metaheuristic based on Taboo search (TS) procedure that makes use of the Scatter search (SS) paradigm. Our objective is to support a TS by a SS add-on to explore the influence of a population and combination strategies on the ability of generating high quality solutions.

REFERENCES

• 1: Roberto Battiti , Marco Protasi, Reactive search, a history-sensitive heuristic for MAX-SAT, Journal of Experimental Algorithmics (JEA), 2, p.2-es, 1997 [doi>10.1145/264216.264220]
• 2: Campus V., Laguna, M., Marti R. Context- independent scatter and tabu search for permutation problems. Document Internet, January 27, 2003.
• 3: Habiba Drias , Mohamed Khabzaoui, Scatter Search with Random Walk Strategy for SAT and MAX-W-SAT Problems, Proceedings of the 14th International conference on Industrial and engineering applications of artificial intelligence and expert systems: engineering of intelligent systems, p.35-44, June 04-07, 2001
• 4: Frank, J A study of genetic algorithms to find approximate solutions to hard 3CNF problems, in proc of Golden Zest international conference on artificial intelligence, 1994.
• 5: Johnson. S, Approximation algorithms for combinatorial problems, Journal of computer and System Sciences 9, 256--278, 1974.
• 6: Pierre Hansen , Brigitte Jaumard, Algorithms for the maximum satisfiability problem, Computing, v.44 n.4, p.279-303, Feb. 4, 1990 [doi>10.1007/BF02241270]
• 7: Glover. F. Taboo search: Part I, ORSA, journal on computing, 1989.
• 8: Glover. F. Genetic algorithms, evolutionary algorithms and scatter search: changing tides and untapped potentials. Technical report. Graduate School of Business, University of Colorado, Boulder, long version of INFORMS CSTS Newsletter 19(1) 1998.
• 9: Laguna M, Glover. F Scatter Search. Internet Document Graduate school of business, University of Colorado, Boulder August 16, 1999.
• 10: Masure B Sais l Greroire, E. A Taboo search for Sat in proceedings of AAAI 1997.
• 11: Panos M. Pardalos , Leonidas S. Pitsoulis , Mauricio G. C. Resende, A Parallel GRASP for MAX-SAT Problems, Proceedings of the Third International Workshop on Applied Parallel Computing, Industrial Computation and Optimization, p.575-585, August 18-21, 1996

INDEX TERMS

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Hybrid metaheuristic, Max-W-Sat, SAT, Scatter search, Solution combination method, Taboo Search