Multi-Core Solver for Discrete Finite-Domain Constraint Satisfaction Problems

Ibrahimi, Erblin (2021) Multi-Core Solver for Discrete Finite-Domain Constraint Satisfaction Problems. Bachelor's Thesis, Computing Science.

Preview	Text bCS_2021_IbrahimiE.pdf Download (1MB) | Preview
	Text Toestemming.pdf Restricted to Registered users only Download (91kB)

Abstract

This thesis presents an implementation of a general-purpose, multi-core solver for finite-domain Constraint Satisfaction Problems (CSPs) that runs efficiently on all multi-core machines, including personal computers. This solver reads input CSPs from a small, custom-designed specification language that provides the user a flexible way of specifying CSPs. The first part of the thesis covers some of the most popular example CSPs and how the backtracking search algorithm, including heuristics and inferences, can be used to solve CSPs. Next, we look at how this algorithm can be parallelized by starting the searching process on multiple threads, each starting at a different variable. This approach leads to duplicate searches between threads, however. We discuss how custom search trees can be used to store partial states that have already been covered to avoid these duplicate searches, and what the drawbacks are of using these trees. We then look at the specification language itself and what features are implemented. We will show how the aforementioned example CSPs can be represented in this language, followed by a section on how the CSP solver works under the hood. Lastly, we analyse the performance of the solver, using different settings for each example CSP, and conclude that there is a speed-up for the majority of these CSPs.

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Meijster, A. and Gattinger, B.R.M.
Degree programme:	Computing Science
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	02 Aug 2021 09:23
Last Modified:	06 Aug 2021 14:35
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/25554

Actions (login required)

View Item