Skip to main content

Research Repository

Advanced Search

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

Djenouri, Youcef; Habbas, Zineb; Djenouri, Djamel

Authors

Youcef Djenouri

Zineb Habbas



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

Files

Data Mining-Based Decomposition for Solving the MAXSAT Problem: Toward a New Approach (140 Kb)
PDF

Licence
http://www.rioxx.net/licenses/all-rights-reserved

Publisher Licence URL
http://www.rioxx.net/licenses/all-rights-reserved

Copyright Statement
(c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.





You might also like



Downloadable Citations