Problem structure and multi-move local search: Criticality and parallelism revisited
Andrea Roli · 2007
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 phenomenon called criticality and parallelism, first discovered in combinatorial optimization problems such as the TSP and NK-models [6]. The main result is that increasing parallelism leads to better solutions, but up to a degree at which the solution quality degrades. Moreover, the optimal parallelism is negatively correlated with the system connectivity.