Empirical analysis of local search algorithms and problem difficulty in satisfiability.
Published: 2006
Language: eng
Number of pages: 148
ISBN-13: 9780494212950
Description: The central thesis of this dissertation is that an empirical analysis leads to a deeper understanding of local search methods and problem difficulty in satisfiability (SAT) and that the understanding can form a foundation for better algorithm designs. The investigation of problem difficulty for local search algorithms has received much attention from researchers, and this work is a continuation of such effort.We provide evidence that the decrease in the local search cost in the over-constrained region for satisfiable instances is largely due to the effects of less extensive high-quality local minima compared to the under- and critically-constrained region. We also show that a backbone-guided local search algorithm works well for over-constrained instances because of its robustness to backbone estimation. Finally, our results from problem difficulty lead to the integration of path relinking with existing local search algorithms, which is demonstrated to be effective on various problem domains.
Notes: Source: Masters Abstracts International, Volume: 45-03, page: 1654.

Thesis (M.A.Sc.)--University of Toronto, 2006.

Electronic version licensed for access by U. of T. users.

ROBARTS MICROTEXT copy on microfiche.