Menninga, Wouter (2022) Solving Constraint Satisfaction Problems in a Distributed Setting. Master's Thesis / Essay, Computing Science.
|
Text
mCS_2022_MenningaWG.pdf Download (1MB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
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 |