Tags:arc consistency, constraint satisfaction, local consistency, neighbourhood singleton arc consistency, preprocessing and singleton arc consistency
Abstract:
Preprocessing a constraint satisfaction problem is a much studied meth-od for improving the performance of subsequent solution search. The traditional explanation for its beneficial effects is problem reduction, where possible values that cannot take part in a solution are discarded, leaving fewer possibilities to explore during search. Here, we show that this is not the only or even the main factor when dynamic variable ordering heuristics are used. Multiple lines of evidence indicate that under these conditions domain reductions effected by preprocessing serve to inform the heuristic as to which variables should be chosen for instantiation before others. An information transmission model is described that can potentially model such effects, and it is shown that an extension of this model can incorporate simple domain reduction effects as well.
Explaining the Effects of Preprocessing on Constraint Satisfaction Search