Les problèmes d’optimisation combinatoire sont généralement réputés NP-difficiles, donc il n’y a pas d’algorithmes efficaces pour les résoudre. Afin de trouver des solutions optimales locales ou réalisables, on utilise souvent des heuristiques ou des algorithmes approchés. Les dernières décennies ont vu naitre des méthodes approchées connues sous le nom de métaheuristiques, et qui permettent de trouver une solution approchées. Cette thèse propose de résoudre des problèmes d’optimisation déterministe et stochastique à l’aide de métaheuristiques. Nous avons particulièrement étudié la méthode de voisinage variable connue sous le nom de VNS. Nous avons choisi cet algorithme pour résoudre nos problèmes d’optimisation dans la mesure où VNS permet de trouver des solutions de bonne qualité dans un temps CPU raisonnable. Le premier problème que nous avons étudié dans le cadre de cette thèse est le problème déterministe de largeur de bande de matrices creuses. Il s’agit d’un problème combinatoire difficile, notre VNS a permis de trouver des solutions comparables à celles de la littérature en termes de qualité des résultats mais avec temps de calcul plus compétitif. Nous nous sommes intéressés dans un deuxième temps aux problèmes de réseaux mobiles appelés OFDMA-TDMA. Nous avons étudié le problème d’affectation de ressources dans ce type de réseaux, nous avons proposé deux modèles : Le premier modèle est un modèle déterministe qui permet de maximiser la bande passante du canal pour un réseau OFDMA à débit monodirectionnel appelé Uplink sous contraintes d’énergie utilisée par les utilisateurs et des contraintes d’affectation de porteuses. Pour ce problème, VNS donne de très bons résultats et des bornes de bonne qualité. Le deuxième modèle est un problème stochastique de réseaux OFDMA d’affectation de ressources multi-cellules. Pour résoudre ce problème, on utilise le problème déterministe équivalent auquel on applique la méthode VNS qui dans ce cas permet de trouver des solutions avec un saut de dualité très faible. Les problèmes d’allocation de ressources aussi bien dans les réseaux OFDMA ou dans d’autres domaines peuvent aussi être modélisés sous forme de problèmes d’optimisation bi-niveaux appelés aussi problèmes d’optimisation hiérarchique. Le dernier problème étudié dans le cadre de cette thèse porte sur les problèmes bi-niveaux stochastiques. Pour résoudre le problème lié à l’incertitude dans ce problème, nous avons utilisé l’optimisation robuste plus précisément l’approche appelée « distributionnellement robuste ». Cette approche donne de très bons résultats légèrement conservateurs notamment lorsque le nombre de variables du leader est très supérieur à celui du suiveur. Nos expérimentations ont confirmé l’efficacité de nos méthodes pour l’ensemble des problèmes étudiés. / Combinatorial optimization problems are generally NP-hard problems, so they can only rely on heuristic or approximation algorithms to find a local optimum or a feasible solution. During the last decades, more general solving techniques have been proposed, namely metaheuristics which can be applied to many types of combinatorial optimization problems. This PhD thesis proposed to solve the deterministic and stochastic optimization problems with metaheuristics. We studied especially Variable Neighborhood Search (VNS) and choose this algorithm to solve our optimization problems since it is able to find satisfying approximated optimal solutions within a reasonable computation time. Our thesis starts with a relatively simple deterministic combinatorial optimization problem: Bandwidth Minimization Problem. The proposed VNS procedure offers an advantage in terms of CPU time compared to the literature. Then, we focus on resource allocation problems in OFDMA systems, and present two models. The first model aims at maximizing the total bandwidth channel capacity of an uplink OFDMA-TDMA network subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. For this problem, VNS gives tight bounds. The second model is stochastic resource allocation model for uplink wireless multi-cell OFDMA Networks. After transforming the original model into a deterministic one, the proposed VNS is applied on the deterministic model, and find near optimal solutions. Subsequently, several problems either in OFDMA systems or in many other topics in resource allocation can be modeled as hierarchy problems, e.g., bi-level optimization problems. Thus, we also study stochastic bi-level optimization problems, and use robust optimization framework to deal with uncertainty. The distributionally robust approach can obtain slight conservative solutions when the number of binary variables in the upper level is larger than the number of variables in the lower level. Our numerical results for all the problems studied in this thesis show the performance of our approaches.

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois. / We adapt a general variable neighborhood search heuristic to solve the traveling salesman problem with time windows (TSPTW) where the objective is to minimize the completion time. We use efficient methods to check the feasibility and the profitability of a movement. We use a specific order to reduce the search space while exploring the neighborhoods. The resulting method is competitive with the state-of-the-art. We improve the best known solutions for two classes of instances and provide the results of multiple instances of TSPTW for the first time.

Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature. / This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are first stage implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.This thesis also includes new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving. Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics. The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND) problem. The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.