When the decomposition meets the constraint satisfaction problem

Djenouri, Youcef; Djenouri, Djamel; Habbas, Zineb; Lin, Jerry Chun-Wei; Michalak, Tomasz P.; Cano, Alberto

Abstract

This paper explores the joint use of decomposition methods and parallel computing for solving constraint satisfaction problems and introduces a framework called Parallel Decomposition for Constraint Satisfaction Problems (PD-CSP). The main idea is that the set of constraints are first clustered using a decomposition algorithm in which highly correlated constraints are grouped together. Next, parallel search of variables is performed on the produced clusters in a way that is friendly for parallel computing. In particular, for the first step, we propose the adaptation of two well-known clustering algorithms ( k -means and DBSCAN). For the second step, we develop a GPU-based approach to efficiently explore the clusters. The results from the extensive experimental evaluation show that the PD-CSP provides competitive results in terms of accuracy and runtime.

Citation

Djenouri, Y., Djenouri, D., Habbas, Z., Lin, J. C., Michalak, T. P., & Cano, A. (2020). When the decomposition meets the constraint satisfaction problem. IEEE Access, 8, 207034-207043. https://doi.org/10.1109/access.2020.3038228

• Journal Article Type: Article
• Acceptance Date: Nov 4, 2020
• Online Publication Date: Nov 16, 2020
• Publication Date: 2020
• Deposit Date: Apr 8, 2021
• Publicly Available Date: Apr 9, 2021
• Journal: IEEE Access
• Electronic ISSN: 2169-3536
• Publisher: Institute of Electrical and Electronics Engineers (IEEE)
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Pages: 207034-207043
• DOI: https://doi.org/10.1109/access.2020.3038228
• Keywords: General Engineering; General Materials Science; General Computer Science
• Public URL: https://uwe-repository.worktribe.com/output/7249369