To main content

When the Decomposition Meets the Constraint Satisfaction Problem

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.
Read the publication

Category

Academic article

Language

English

Author(s)

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

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics
  • Université de Lorraine
  • University of Warsaw
  • University of the West of England, Bristol
  • Western Norway University of Applied Sciences
  • Algeria
  • Virginia Commonwealth University

Year

2020

Published in

IEEE Access

Volume

8

Page(s)

207034 - 207043

View this publication at Norwegian Research Information Repository