Travelling in the World of Local Searches in the Space of Partial Assignments

In this paper, we report the main results of a study which has been carried out about the multiple ways of parameterising a local search in the space of the partial assignments of a Constraint Satisfaction Problem (CSP), an algorithm which is directly inspired from the decision repair algorithm [1]. After a presentation of the objectives of this study, we present the generic algorithm we started from, the various parameters that must be set to get an actual algorithm, and some potentially interesting algorithm instances. Then, we present experimental results on randomly generated, but not completely homogeneous, binary CSPs, which show that some specific parameter settings allow such a priori incomplete algorithms to solve almost all the consistent and inconsistent problem instances on the whole constrainedness spectrum. Finally, we conclude with the work that remains to do if we want to acquire a better knowledge of the best parameter settings for a local search in the space of partial assignments.