en fr Tabu-NG: hybridization of constraint programming and local search for solving CSP Tabu-NG : hybridation de programmation par contraintes et recherche locale pour la résolution de CSP Report as inadecuate




en fr Tabu-NG: hybridization of constraint programming and local search for solving CSP Tabu-NG : hybridation de programmation par contraintes et recherche locale pour la résolution de CSP - Download this document for free, or read online. Document in PDF available to download.

1 SET - Laboratoire Systèmes et Transports

Abstract : A very large number of combinatorial problems belong to the family of Constraint Satisfaction Problems CSP: configuration, planning, scheduling, resource allocation

. These problems share a common description that generally allows a clear and intuitive modeling. In this thesis, we proposed and studied a new hybrid method for solving CSPs. We named this method Tabu-NG for Tabu Search based on NoGood. The name is a bit simplistic because it is a hybrid of filtering algorithm, constraint propagation, Tabu Search and nogood management. The method was applied to two types of problems. The first is the Frequency Assignment Problem FAP in military radio networks, particularly the problems proposed from 1993 benchmarks of the European project CALMA until 2010 benchmarks of a DGA project. The second is the academic problem of k-coloring of graphs on the DIMACS instances. The method has improved some high scores currently known. In both problems we dealt with unary and binary constraints, and also with n-ary constraints and function optimization under constraints for FAP. The principles of Tabu-NG are general and can be applied to other CSPs. It can also accommodate specific heuristics to problems, we practiced it on the problems cited, and in this sense we believe we can qualify the method as metaheuristic without abusing this definition.

Résumé : Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes Constraint Satisfaction Problem ou CSP : configuration, ordonnancement, affectation de ressources

. Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s-agit d-une hybridation d-algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été appliquée sur deux types de problèmes. Le premier est l-affectation des fréquences FAP dans les réseaux de radiocommunications militaires, en particulier les problèmes proposés de 1993 instances du projet européen CALMA jusqu-à 2010 instances d-un projet DGA. Le deuxième est le problème académique de k-coloration de graphes sur les instances DIMACS. La méthode a amélioré quelques meilleurs scores connus actuellement. Dans les deux problèmes nous avons traité des contraintes unaires et binaires, ainsi que des contraintes n-aires et de l-optimisation de fonction sous contraintes pour le FAP. Les principes de Tabu-NG sont généraux et elle peut s-appliquer sur d-autres CSP. Elle peut par ailleurs accueillir des heuristiques spécifiques aux problèmes, nous l-avons pratiqué sur les problèmes cités, et en ce sens nous pensons pouvoir qualifier la méthode de métaheuristique sans abuser de cette définition.

en fr

Keywords : Graph coloring local search hybridization betwwen constraint programming and local search complexity metaheuristics frequency assignment problem

Mots-clés : Computer Science-Software Engineering and Symbolic Computing CSP métaheuristiques méthodes exactes FAP coloration de graphe hybridation PPC et recherche locale





Author: Mohammad Dib -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents