Empirical analysis of local search algorithms and problem difficulty in satisfiabilit

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.