An Improved Local Search Method for the MAX-SAT Problem
Wenxing Zhu · Computer Engineering and Science · 2008
Local search methods are efficient for solving the large-scale SAT problem.Classic local search algorithms such as GSAT,WSAT,TSAT,NSAT build initial solutions randomly.In this paper,the initial probability obtained by the simplex algorithm is put forward,which can constrain the random initial assignment of variables in the construction phase of the local search method.The strategies are helpful in increasing the number of satisfied clauses at the beginning of local search and in making the local search convergence fast.Compared with the classic local search algorithms,the experimental results show that the proposed algorithm improves the efficiency of solving the SAT problem and performs well in many instances.