Using Arc Weights to Improve Iterative Repair

Abstract

One of the surprising findings from the study of CNF sat-isfiability in the 1990’s has been the success of iterative repair techniques, and in particular of weighted iterative repair. However, attempts to improve weighted iterative repair have either produced marginal benefits or rely on domain specific heuristics. This paper introduces a new extension of constraint weighting called Arc Weighting Iterative Repair, that is applicable outside the CNF domain and can significantly improve the performance of cons-traint weighting. The new weighting strategy extends constraint weighting by additionally weighting the con-nections or arcs between constraints. These arc weights represent increased knowledge of the search space and can be used to guide the search more efficiently. The main aim of the research is to develop an arc weighting algorithm that creates more benefit than overhead in reducing moves in the search space. Initial empirical tests indicate the algorithm does reduce search steps and times for a se-lection of CNF and CSP problems.