Skip to main content

Research Repository

Advanced Search

When the decomposition meets the constraint satisfaction problem

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

When the decomposition meets the constraint satisfaction problem Thumbnail


Authors

Youcef Djenouri

Zineb Habbas

Jerry Chun-Wei Lin

Tomasz P. Michalak

Alberto Cano



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

Files





You might also like



Downloadable Citations