Partitioning Search Spaces of a Randomized Search

Reference:

Antti E. J. Hyvärinen, Tommi Junttila, and Ilkka Niemelä. Partitioning search spaces of a randomized search. Technical Report TKK-ICS-R22, Helsinki University of Technology, Department of Information and Computer Science, Espoo, Finland, November 2009.

Abstract:

This work studies the following question: given an instance of the propositional satisability problem, a randomized satisability 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 (unsatisable, satisable with few solutions, and satisable 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.

Keywords:

Constraint-based Search, Distributed Search, Randomized Search, Search-Space Partitioning, SAT Solvers

Suggested BibTeX entry:

@techreport{TKK-ICS-R22,
    address = {Espoo, Finland},
    author = {Antti E. J. Hyv{\"a}rinen and Tommi Junttila and Ilkka Niemel{\"a}},
    institution = {Helsinki University of Technology, Department of Information and Computer Science},
    month = {November},
    number = {TKK-ICS-R22},
    pages = {22},
    title = {Partitioning Search Spaces of a Randomized Search},
    type = {Technical Report},
    year = {2009},
}