Then necessary backtrack and explore alter-native assignments

344 Konstantinos Chatzikokolakis et al.

Especially in [6], the reparative process is guided by conflict-based heuristics and is coupled with tabu search. Our general CR framework encompasses such ap-proaches while not being restricted to a specific repair operator. In CNR-search, the repair operator does not employ backtracking.

function generates possible extensions of the current partial assignment		re-

3 Reparative Search

Reparative methods iteratively modify an inconsistent complete assignment un-til a consistent complete assignment is obtained. Because of the fact that search is performed exclusively in the space of complete assignments, the features of reparative methods are complementary to those of constructive ones. The search process is endowed with flexibility, since it is possible to perform arbitrary leaps to complete assignments throughout the search space. However, systematic ex-ploration of the search space and completeness are forsaken, consistency tech-niques can no longer be exploited and the search process is particularly sensitive to the existence of local optima.

4 Search by Construction and Repair

In this section, we discuss a generic search framework which incorporates both construction and repair operators. Intuitively, search is to be performed in two alternating stages: