关键词: MAX-SAT问题 局部搜索 单纯形法

Abstract:

Local search methods are efficient for solving the large-scale SAT problem. Classic local search algorithms such as GSAT,WSAT, TSAT, NSAT build initia  l solutions randomly. In this paper, the initial probability obtained by the simplex algorithm is put forward, which can constrain the random initial as  signment 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 resul   ts show that the proposed algorithm improves the efficiency of solving the SAT problem and performs well in many instances.

Key words: MAX-SAT problem, local search, simplex method