Advanced generic neighborhood heuristics for VNS

Weighted CSP (Constraint Satisfaction Problems) are used to model and to solve constraint optimization problems. As most WCSP are solved by local search methods that use large neighborhoods, selecting the neighborhood to explore is crucial. However, designing efficient neighborhoods is difficult and problem dependent. The very few generic heuristics defined for CSP , as ConflictVar or H-PGLNS, are not well suited for WCSP . In this paper, we propose new generic neighborhood heuristics dedicated to WCSP . Our heuristics take advantage of both conflicted variables and the topology of the constraints graph. We define the concept of freedom degree of a variable to make a compromise between these two criteria, and introduce a diversification criterion by choosing non-conflicted variables connected to conflicted ones. Then we extend, in a systematic way, each proposed heuristic in order to take into account violation costs of constraints. Experiments have been performed on real life instances (RLFAP) as well as random instances (GRAPH and Kbtree) using VNS/LDS+CP (a particular instance of VNS we developed). Experiments show that our generic heuristics clearly outperform ConflictVar and H-PGLNS. Among all topological heuristics we proposed, ConflictVar-MaxDeg appears to be the best one.