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

Djenouri, Youcef; Habbas, Zineb; Djenouri, Djamel

Abstract

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

• Journal Article Type: Article
• Acceptance Date: Dec 16, 2016
• Online Publication Date: Aug 17, 2017
• Publication Date: Sep 1, 2017
• Deposit Date: Jan 21, 2020
• Publicly Available Date: Jan 23, 2020
• Journal: IEEE Intelligent Systems
• Print ISSN: 1541-1672
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 32
• Issue: 4
• Pages: 48-58
• DOI: https://doi.org/10.1109/MIS.2017.3121546
• Public URL: https://uwe-repository.worktribe.com/output/5198130
• Publisher URL: https://ieeexplore.ieee.org/document/8012345