Generic hybrid algorithms for solving constraint satisfaction problems

In this paper, we present a generic hybrid algorithm for combining complete (constraint programming) and incomplete (local search) methods in order to solve constraint satisfaction problems. This algorithmic scheme uses constraint propagation techniques and local search heuristics over populations. The structures involved provide a harmonious interaction between the different methods, and also benefit from the respective methods' assets. We propose various combination strategies and emphasize their interest on some examples which are solved by means of an implementation.