Partitioning search spaces of a randomized search
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Faculty of Information and Natural Sciences |
D4 Julkaistu kehittämis- tai tutkimusraportti taikka -selvitys
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
2009
Major/Subject
Mcode
Degree programme
Language
en
Pages
22
Series
TKK reports in information and computer science, 22
Abstract
This work studies the following question: given an instance of the propositional satisfiability problem, a randomized satisfiability solver, and a cluster of n computers, what is the best way to use the computers to solve the instance? Two approaches, simple distribution and search space partitioning as well as their combinations are investigated both analytically and empirically. It is shown that the results depend heavily on the type of the problem (unsatisfiable, satisfiable with few solutions, and satisfiable with many solutions) as well as on how good the search space partitioning function is. In addition, the behavior of a real search space partitioning function is evaluated in the same framework. The results suggest that in practice one should combine the simple distribution and search space partitioning approaches.Description
Keywords
constraint-based search, distributed search, randomized search, search-space partitioning, SAT solvers