Problem structure and multi-move local search: Criticality and parallelism revisited

TL;DRAbstract

The impact of problem structure on search is a relevant issue in AI research and related areas. This topic has been recently received more attention, due to the following reasons: (i) real-world problems are often more difficult to solve than random generated problems of the same size and (ii) results obtained by applying statistical mechanics techniques (such as phase transition analysis [3]) have shown a strong correlation between search effectiveness and some critical parameters of the instances at hand. In this work we investigate the relation between some SAT/MAXSAT instance features and the behavior of local search. We will define structural features on the basis of a constraint graph associated to the instances and in particular we will deeply investigate the impact of the node degree frequency on the behavior of multi-move local search —also known as parallel local search, as more than one local move is applied synchronously at each iteration. This work is inspired by a phenome

Chat with Paper

AI Agents for this Paper