Heuristiques de recherche pour la résolution des WCSP
Institution:
CaenDisciplines:
Directors:
Abstract EN:
Weighted Constraint Satisfaction Problem (WCSP) which are a generalization to the optimization of CSP, are usually solved by tree search methods combined with filtering algorithms or local search methods. Although many generic heuristics have been proposed for such methods in the CSP framework, this is not the case for WCSP yet. Our objective was to define and implement new generic heuristics dedicated to WCSP in order to efficiently guide search methods. For tree search methods, we have proposed several value ordering and variable ordering heuristics based on a global criterion, the H-Quality, which is less dependent on filtering mechanisms. For VNS based metaheuristics, we have proposed new neighborhood heuristics based on the concept of degree of freedom wich depend on the topology of graph of constraints. Then, we have proposed to extend them to the WCSP framework in order to take into account cost of constraints. In order to validate our contribution, we have made experiments on real-world problems (Radio Link Frequency Assignment Problem) (CELAR), random structured instances (GRAPH) and random instances. From these experiments, it appears that the concept of H-Quality is a relevant criterion to guide value ordering heuristics and interesting to guide variable ordering heuristics for high connectivity and high density instances. Neighborhood heuristics based degree of freedom and taking into account cost constraints offer better performance.
Abstract FR:
Les Weighted Constraint Satisfaction Problem (WCSP) qui sont une généralisation à l’optimisation des CSP, sont souvent résolus par des méthodes de recherche arborescentes combinées avec des algorithmes de filtrage ou recherches locales. Bien que de nombreuses heuristiques génériques aient été proposées dans les CSP, cela est loin d’être le cas pour les WCSP. L’objectif de ce travail consistait à mettre en oeuvre de nouvelles heuristiques génériques, adaptées aux WCSP et guidant efficacement les méthodes de résolution. Pour les recherches arborescentes, nous avons proposé plusieurs heuristiques de choix de valeur et de variable basées sur un critere global, la H-Quality, moins indépendant du mécanisme de filtrage (critère local). Pour les méta-heuristiques à voisinage variable (VNS), nous avons proposé diféerentes heuristiques de voisinage basées sur la notion de degré de liberté qui dépendent de la topologie du graphe de contraintes. Puis, nous avons proposé d'étendre celles-ci aux WCSP afin de tenir compte du coût des contraintes. Afin de valider nos contributions, nous avons réalisé des expérimentations sur des problèmes réels d’affectation de liens radio (CELAR), aléatoires avec structures (GRAPH) et purement alétoires. De ces expérimentations, il ressort que le critère d’H-Quality est pertinent pour guider les heuristiques de choix de valeur, et intéressant pour les heuristiques de choix de variable sur les instances à forte connectivité et forte densité. Les heuristiques de choix de voisinage augmentant le degré de liberté des variables et tenant compte des coûts des contraintes offrent de meilleurs résultats.