Backtracking with Tree Decomposition for Solving Constraint Optimization Problems

Nguyen, Tran Duy hieu (2022) Backtracking with Tree Decomposition for Solving Constraint Optimization Problems. Bachelor's Thesis, Computing Science.

Preview	Text bCS_2022_NguyenTDH.pdf Download (2MB) | Preview
	Text toestemming.pdf Restricted to Registered users only Download (122kB)

Abstract

Solving Constraint Satisfaction Problems (CSP) and its sibling the Constraint Optimization Problems (COP) is a prominent research subject in Computing Science in general and in Artificial Intelligence in particular. A notable technique for solving CSPs is using the decomposition of the problem to divide it into independent sub-problems. The algorithm Backtracking with Tree Decomposition (BTD) was developed to solve CSP using the tree decomposition of the constraint network between the variables. In this thesis, we explored the idea of using BTD as a method to solve optimisation problems. We designed and implemented the BTD* algorithm which performs recursive search on the tree decomposition of the constraint network. Following the structure of the tree decomposition, BTD* tries to find the optimal solution to the problem by recursively optimizing the cost of the subtrees until it has determined that no other solution can be more optimized than the one last found, or until it has proven that the problem is unsatisfiable. We then made comparisons between BTD* and the existing COP solver Choco by performing benchmarks using 96 instances selected from the website of the XCSP3 framework. Based on these comparisons, we determined that the performance of BTD* is not comparable to that of the Choco solver, both in terms of time complexity and space complexity. Even though our algorithm and implementation is not entirely efficient, it is still a good starting point for future research

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Lazovik, A. and Medema, M.
Degree programme:	Computing Science
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	01 Sep 2022 10:25
Last Modified:	01 Sep 2022 10:25
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/28632

Actions (login required)

View Item