A new template concept to guide the local search: case of maximal constraint satisfaction problems

Abstract within constraint satisfaction problems (CSPs), our work proposes a new search heuristic. The latter is basically inspired by the template concept introduced by E.P.K. TSANG. It consists of a new template concept and could be classified as a min-conflict heuristic. In this paper we introduce a new guided local search that uses our heuristic in local search (LS) for Maximal constraint satisfaction problems (Max-CSPs). Compared to previous well known guided local search, our approach changes experimental results for the better.