Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysés. / The minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed.

Dans cette thèse, nous étudions trois catégories de problèmes : les d-extensibles, les d-bloqueurs et les d-transversaux.Les d-extensibles de stables optimaux sont des ensembles de sommets d'un graphe G tels que tout stable de cardinal d du sous-graphe induit par un d-extensible peut être étendu à un stable optimal de G à l'aide de sommets qui n'appartiennent pas au d-extensible. Nous étudions les d-extensibles de cardinal maximal de stables dans les graphes bipartis. Nous démontrons quelques propriétés structurelles puis nous déterminons une borne inférieure du cardinal maximal d'un d-extensible. Nous étudions quelques classes de graphes dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial. Nous nous intéressons ensuite aux d-extensibles de stables dans les arbres. Nous prouvons plusieurs propriétés structurelles, déterminons une autre borne inférieure du cardinal maximal d'un d-extensible et étudions quelques classes d'arbres dans lesquelles déterminer un d-extensible optimal de stables est un problème polynomial.Les d-bloqueurs de stables sont des ensembles de sommets d'un graphe G tels que, si on retire les sommets d'un d-bloqueur, le cardinal maximal d'un stable du graphe induit par les sommets restants est inférieur d'au moins d au cardinal maximal d'un stable du graphe initial. Nous nous intéressons ici aux d-bloqueurs de coût minimal de stables dans les arbres. Après avoir prouvé une caractérisation des d-bloqueurs de stables dans les arbres, nous démontrons que déterminer un d-bloqueur de coût minimal de stable est un problème polynomial dans une classe d'arbres particulière.Soit Pi un problème d'optimisation sur un ensemble d'éléments fini. Un d-transversal de Pi est un ensembles d'éléments tel que l'intersection entre le d-transversal et toute solution optimale au problème Pi est de cardinal supérieur égal à d. Nous proposons ici une approche de génération de contraintes pour déterminer des d-transversaux de cardinal maximal de problèmes modélisés par des programmes mathématiques en variables binaires. Nous étudions deux variantes de cette approche que nous testons sur des instances de graphes générés aléatoirement pour déterminer des d-transversaux de stables optimaux et des d-transversaux de couplages optimaux / In this thesis, we study three types of problems : the d-extensibles sets, the d-blockers and the d-transversals.In a graph G, a d-extensible set of maximum independent sets is a subset of vertices of G such that every stable set of cardinality d in the subgraph restricted to the d-extensible set can be extented to a maximum stable set of G using only vertices that do not belong to the d-extensible set. We study d-extensible sets of mxaimum cardinality of stable sets in bipartite graphs. We show some structural properties and we determine a lower bound of the maximum cardinality of a d-extensible set. We consider some classes of graph where finding an optimum d-extensible set can be done in polynomial time. Then, we study the d-extensibles sets of stable sets in trees. We prove some properties on the structures of the d-extensibles sets and we determine another lower bound of the maximum cardinality of a d-extensible set. Finaly, we study somme classes of tree where a d-extensible sets of maximum cardinality can be done in polynomial time.In a graph G, a d-blocker is a subset of vertices such that, if removed, a maximum stable set of the resulting subgraph is of cardinality at most the cardinality of a maximum stable set of G minus d. We study d-blocker of minimal cost of stable sets in tree.We prove a caracterisation of d-blockers in tree and we study a particular classe of trees where computing a d-blocker of minimal cost of stable sets can be done in polynomial time.Let Pi be an optimisation problem on a finite set of elements. A d-transversal of Pi is a subset of elements such that the intersection between the d-transversal and every optimal solution of Pi contains at lest d elements. We propose an approach to compute d-transversal of any optimisation problem modelised by mathematical program with binary variables. We use a contraints generation approach. We compare two variations of this approach on randomly generated graph by computing d-transversals of stables sets and d-transversals of matching