A Penalty Function Approach to Max 3-SAT Problems

We consider a penalty function approach for the solving of the Max 3-SAT problem. The algorithm introduced is a multi-start approach that makes use of elite-solution techniques derived from scatter search. More precisely, it is based on the so-called adaptive memory projection metaphor. The main focus of this paper is to demonstrate the usefulness of this projection idea in the context of the binary Max 3-SAT. We review the literature in that field, explain the metaheuristic proposed and present results on the basis of a DIMACS test set.