Advanced generic neighborhood heuristics for VNS
Weighted CSP CSP (Constraint Satisfaction Problems) are used to model and to solve constraint optimization problems. As most WCSP 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 CSP , as ConflictVar or H-PGLNS, are not well suited for WCSP WCSP . In this paper, we propose new generic neighborhood heuristics dedicated to WCSP 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.
neighborhood heuristics vns wcsp local search rlfap lns constraint programming maxcsp experimental studies