Using local search to speed up filtering algorithms for some NP‐hard constraints

This paper proposes to use local search inside filtering algorithms of combinatorial structures for which achieving a desired level of consistency is too computationally expensive. Local search quickly provides supports for many variable‐value pairs, thus reducing the effort required to check and potentially filter the rest of them. The idea is demonstrated on the SomeDifferent constraint, a graph coloring substructure. An experimental evaluation confirms its significant computational gain in many cases.