Simulating game playing to solve Max-SAT
Chenchen Ding, Jinlong Li · 2018
The Max-SAT can naturally model many practical optimization problems. In this paper, we propose an incomplete Max-SAT algorithm bgmaxsat, which utilizes boolean game to model and solve Max-SAT problems. Then we improve bgmaxsat by adding a new agents grouping criterion to solve massive instances, called bgmaxsat_m. In order to obtain quality solution quickly, we design two mechanisms to accelerate the game playing. Finally, we evaluate our algorithms against with the state-of-the-art SLS-based algorithms CCLS and Swcca-ms on 87 selected Max-SAT instances. The experimental results show that bgmaxsat finds optimal solutions on 65(65) general instances with competitive CPU time, and bgmaxsat_m finds better solutions on 19(22) massive instances with less CPU time.