Javascript must be enabled for the correct page display

Solving Constraint Satisfaction Problems in a Distributed Setting

Menninga, Wouter (2022) Solving Constraint Satisfaction Problems in a Distributed Setting. Master's Thesis / Essay, Computing Science.

[img]
Preview
Text
mCS_2022_MenningaWG.pdf

Download (1MB) | Preview
[img] Text
toestemming.pdf
Restricted to Registered users only

Download (122kB)

Abstract

Solving constraint satisfaction problems (CSPs) is an NP-complete problem. Many algorithms exist for solving CSPs, some of which make use of parallelization. However, such algorithms are restricted by the amount of resources that can be available on a single machine. Therefore, this thesis implements a distributed approach for solving a CSP, using the actor model. In our work, an adapted, distributed version of the BTD algorithm was implemented using the actor model. Experiments using the implemented algorithm show that the solve time for a problem is reduced logarithmically when increasing the number of cores, while it grows linearly when increasing the number of nodes. The original CSP is decomposed into subproblems by means of tree decomposition. Different strategies for deploying these subproblems among the cluster nodes are explored. We found that the deployment strategy has a large impact on the solve time. The best strategy is dependent on the structural properties of the problem being solved. Moreover, we found that taking into account the separator size during the deployment, by deploying nodes in the tree decomposition that share a large separator to the same machine, has a considerable beneficial impact on the solve time of up to 24%. Finally, we show that the method of decomposition has a high impact on the achieved scalability.

Item Type: Thesis (Master's Thesis / Essay)
Supervisor name: Lazovik, A. and Medema, M.
Degree programme: Computing Science
Thesis type: Master's Thesis / Essay
Language: English
Date Deposited: 16 May 2022 10:06
Last Modified: 16 May 2022 10:06
URI: https://fse.studenttheses.ub.rug.nl/id/eprint/27057

Actions (login required)

View Item View Item