Solving weighted Max-Sat optimization problems using a Taboo Scatter Search metaheuristic
Dalila Boughaci, Habiba Drias · 2004
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.