Change search
ReferencesLink to record
Permanent link

Direct link
String Variables for Constraint-Based Local Search
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computing Science.
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

String variables occur as a natural part of many computationally challenging problems. Usually, such problems are solved using problem-specific algorithms implemented from first principles, which can be a time-consuming and error-prone task. A constraint solver is a framework that can be used to solve computationally challenging problems by first declaratively defining the problem and then solving it using specialised off-the-shelf algorithms, which can cut down development time significantly and result in faster solution times and higher solution quality. There are many constraint solving technologies, one of which is constraint-based local search (CBLS). However, very few constraint solvers have native support for solving problems with string variables. The goal of this thesis is to add string variables as a native type to the CBLS solver OscaR/CBLS. The implementation was experimentally evaluated on the Closest String Problem and the Word Equation System problem. The evaluation shows that string variables for CBLS can be a viable option for solving string problems. However, further work is required to obtain even more competitive performance.

Place, publisher, year, edition, pages
2016. , 45 p.
Series
IT, 16057
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-301501OAI: oai:DiVA.org:uu-301501DiVA: diva2:954752
Educational program
Master Programme in Computer Science
Supervisors
Examiners
Available from: 2016-08-23 Created: 2016-08-23 Last updated: 2016-08-23Bibliographically approved

Open Access in DiVA

fulltext(1269 kB)9 downloads
File information
File name FULLTEXT01.pdfFile size 1269 kBChecksum SHA-512
f79ea127b23ac0e022be7e21938a3f55310a08dd0c83d1cbee0d6fa305d027ac5a1a354835fcac048e5dea358cfeda0aeadbb8adce44976e39da077720305f25
Type fulltextMimetype application/pdf

By organisation
Division of Computing Science
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 9 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link