Data Mining-Based Decomposition for Solving the MAXSAT Problem: Toward a New Approach

摘要: This article explores advances in the data mining arena to solve fundamental MAXSAT problem. In proposed approach, instance is first decomposed and clustered by using decomposition techniques, then every cluster resulting from separately solved construct a partial solution. All solutions are merged into global one, while managing possible conflicting variables due separate resolutions. The approach has been numerically evaluated on DIMACS instances some hard Uniform-Random-3-SAT instances, compared state-of-the-art based algorithms. results show that considerably improves success rate, with competitive computation time that’s very close of solutions.