| On 2003-11-21 at 15:00:00 (Brussels Time) |
Abstract
The impact of problem structure on search is a relevant issue in AI research and related areas. Among the possible approaches to analyze problem structure, the one referring to constraint graph and similar graphs enables to relate graph parameters and characteristics with search algorithm behavior. In this talk, we present and discuss two examples of the impact of graph structure on the performance of local search (and also exact algorithms) applied to Satisfiability problems (SAT). We first give a definition of the graph associated to SAT instances and we introduce its main parameters and characteristics. In a first session of experiments, we show that the node degree distribution affects the behavior of 'multi-moves' local search and we find empirical evidence for the presence of an optimal number of parallel local moves that enables the algorithm to achieve the highest effectiveness. We also show that the optimal number of parallel moves is negatively correlated with the connectivity among variables. The results obtained can give insight into the Criticality and Parallelism phenomenon and into the behavior of trajectory methods. In the second session, we investigate the hardness of small-world SAT instances, finding results which may support the conjecture that small-world instances are among the hardest to solve for both approximate and complete algorithms.
Keywords
Satisfiability Problem, Local search, Problem structure, Criticality and Parallelism, Small-world
