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 Reportar como inadecuado




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 - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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





Autor: Mohammad Dib -

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



DESCARGAR PDF




Documentos relacionados