L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

La tolérance aux pannes est une propriété très importante des réseaux optiques de nouvelle génération. Cette thèse aborde la conception des mécanismes de protection contre des pannes liées à la défaillance d’une fibre optique ou à une catastrophe naturelle. Deux systèmes de protection classiques, à savoir la protection par des cycles préconfigurés(p-cycles) et la protection du chemin de secours, sont étudiés pour atteindre une efficacité de protection élevée, tout en considérant le coût de l’équipement optique,la consommation d’énergie et l’utilisation de la ressource spectrale. Ces problèmes de survivabilité sont d’abord formulés en utilisant la programmation linéaire en nombres entiers (PLNE), et ensuite résolus soit par algorithmes heuristiques, soit par une approche de décomposition.La panne d’une seule fibre optique est le scénario le plus courant. Nous allons donc considérer d’abord des pannes liées à la défaillance d’une fibre optique dans les réseaux optiques multi-débit. Pour réduire le coût des transpondeurs, un système de protection par p-cycles de longueur adaptable et peu coûteux est proposé. Spécifiquement, les p cycles de longueur limitée sont conçus pour utiliser un débit approprié en fonction du coût du transpondeur et de la portée de transmission. Un modèle de programmation linéaire en nombres entiers (PLNE) sans énumération des cycles candidats est formulé pour générer directement les p-cycles de coût dépenses d’investissement minimum. De plus, un algorithme GPA (Graph Partitioning in Average) et un algorithme d’estimation des nombres de cycles (EI) sont développés pour rendre le modèle PLNE plus efficace au niveau du temps de calcul. En ce qui concerne la consommation d’énergie des réseaux optiques élastiques résilients,nous proposons d’utiliser un schéma de p-cycles dirigés, efficaces en énergie,pour protéger le trafic asymétrique. En raison de l’avantage de distinguer du volume de trafic dans les deux directions, les p-cycles dirigés consomment peu d’énergie en attribuant de créneaux ou slots du spectre et des formats de modulation différents à chaque direction.Un modèle PLNE est formulé pour minimiser la consommation d’énergie totale sous contraintes de génération du cycle dirigée, d’allocation de spectre, d’adaptation de modulation et de capacité de protection. Pour le passage à l’échelle, le modèle PLNE est décomposé en deux sous-problèmes: une méthode d’énumération de cycles améliorée et un modèle PLNE simplifié pour la sélection des cycles. Nous avons montré que les p-cycles dirigés obtiennent une meilleure performance comparant les p-cyclesiii non-dirigés pour le trafic asymétrique en termes de la consommation d’énergie et de l’utilisation du spectre.Afin d’améliorer l’efficacité d’utilisation du spectre dans réseaux optiques élastiques, une protection par p-cycles (SS-p-cycle) à spectre partagé est proposée. Les SS-p-cycles permettent de réduire l’utilisation du spectre et le taux de fragmentation spectrale en exploitant un partage de spectre spécial entre plusieurs p-cycles ayant des liens communs.Les modèles PLNE est conçus dans les cas "sans" ou "avec" conversion spectrale afin de minimiser l’utilisation du spectre. Ces modèles peuvent obtenir la solution optimale pour un petit réseaux optiques élastiques, et une heuristique efficace est développée pour résoudre les instances à grande échelle. Les résultats de simulations montrent que les SS-p-cycles ont des avantages significatifs pour réduire l’utilisation de la ressource spectrale et la défragmentation des fréquence. De plus, la conversion du spectre aide les SS-p-cycles à acquérir une meilleure utilisation du spectre. / Network survivability is a critical issue for optical networks to maintain resilience against network failures. This dissertation addresses several survivability design issues against single link failure and large-scale disaster failure in optical networks. Twoclassic protection schemes, namely pre-configured Cycles (p-Cycle) protection and path protection, are studied to achieve high protection capacity efficiency while taking intoaccount the equipment cost, power consumption and resource usage. These survivable network design problems are first formulated by mathematical models and then offered scalable solutions by heuristic algorithms or a decomposition approach.We first consider single link failure scenario. To cut the multi-line rates transponderscost in survivable Mixed-Line-Rate (MLR) optical networks, a distance-adaptive andlow Capital Expenditures (CAPEX) cost p-cycle protection scheme is proposed withoutcandidate cycle enumeration. Specifically, path-length-limited p-cycles are designed touse appropriate line rate depending on the transponder cost and transmission reach.A Mixed Integer Linear Programming (MILP) model is formulated to directly generate the optimal p-cycles with the minimum CAPEX cost. Additionally, Graph Partitioning in Average (GPA) algorithm and Estimation of cycle numbers (EI) algorithm are developed to make the proposed MILP model scalable, which are shown to be efficient.Regarding the power consumption in survivable Elastic Optical Networks (EONs),power-efficient directed p-cycle protection scheme for asymmetric traffic is proposed.Owing to the advantage of distinguishing traffic amount in two directions, directedp-cycles consume low power by allocating different Frequency Slots (FSs) and modulation formats for each direction. An MILP model is formulated to minimize total power consumption under constraints of directed cycle generation, spectrum assignment,modulation adaptation and protection capacity allocation. To increase the scalability, the MILP model is decomposed into an improved cycle enumeration and a simplified Integer Linear Programming (ILP) model. We have shown that the directedp-cycles out perform the undirected p-cycles in terms of power consumption and spectrum usage.In order to improve the spectrum usage efficiency in p-cycle protection, a SpectrumShared p-cycle (SS-p-cycle) protection is proposed for survivable EONs with and without spectrum conversion. SS-p-cycles permit to reduce spectrum usage and Spectrum Fragmentation Ratio (SFR) by leveraging potential spectrum sharing among multiplep-cycles that have common link(s). The ILP formulations are designed in both cases of with and without spectrum conversion to minimize the spectrum usage of SS-p-cycleswhich can obtain the optimal solution in small instance, and a time-efficient heuristic algorithm is developed to solve large-scale instances. Simulation results show that SSp-cycles have significant advantages on both spectrum allocation and defragmentation efficiency, and the spectrum conversion does help SS-p-cycle design to acquire better spectrum utilization.

Dans le cadre industriel et académique, les méthodologies de développement logiciel exploitent de plus en plus le concept de “modèle” afin d’appréhender la complexité des systèmes temps réel critiques. En particulier, celles-ci définissent une étape dans laquelle un modèle fonctionnel, conçu comme un graphe de blocs fonctionnels communiquant via des échanges de signaux de données, est déployé sur un modèle de plateforme d’exécution matérielle et un modèle de plateforme d’exécution logicielle composé de tâches et de messages. Cette étape appelée étape de déploiement, permet d’établir une architecture opérationnelle du système nécessitant une validation des propriétés temporelles du système. Dans le contexte des systèmes temps réel dirigés par les évènements, la vérification des propriétés temporelles est réalisée à l’aide de l’analyse d’ordonnançabilité basée sur l’analyse des temps de réponse. Chaque choix de déploiement effectué a un impact essentiel sur la validité et la qualité du système. Néanmoins, les méthodologies existantes n’offrent pas de support permettant de guider le concepteur d’applications durant l’exploration de l’espace des architectures possibles. L’objectif de ces travaux de thèse consiste à mettre en place des techniques d’analyse et de synthèse automatiques permettant de guider le concepteur vers une architecture opérationnelle valide et optimisée par rapport aux performances du système. Notre proposition est dédiée à l’exploration de l’espace des architectures en tenant compte à la fois des quatre degrés de liberté déterminés durant la phase de déploiement, à savoir (j) le placement des éléments fonctionnels sur les éléments de calcul et de communication de la plateforme d’exécution, (ii) le partitionnement des éléments fonctionnels en tâches temps réel et des signaux de données en messages, (iii) l’affectation de priorités d’exécution aux tâches et aux messages du système et (iv) l’attribution du mécanisme de protection des données partagées pour les systèmes temps réel périodiques. Nous nous intéressons principalement à la satisfaction des contraintes temporelles et celles liées aux capacités des ressources de la plateforme cible. De plus, nous considérons l’optimisation des latences de bout-en-bout et la consommation mémoire. Les approches d’exploration architecturale présentées dans cette thèse sont basées sur la technique d’optimisation PLNE (programmation linéaire en nombres entiers) et concernent à la fois les applications activées périodiquement et celles dont l’activation est pilotée par les données. Contrairement à de nombreuses approches antérieures fournissant une solution partielle au problème de déploiement, les méthodes proposées considèrent l’ensemble du problème de déploiement. Les approches proposées dans cette thèse sont évaluées à l’aide d’applications génériques et industrielles. / Modern development methodologies from the industry and the academia exploit more and more the ”model” concept to address the complexity of critical real-time systems. These methodologies define a key stage in which the functional model, designed as a network of function blocks communicating through exchanged data signals, is deployed onto a hardware execution platform model and implemented in a software model consisting of a set of tasks and messages. This stage so-called deployment stage allows establishment of an operational architecture of the system, thus it requires evaluation and validation of the temporal properties of the system. In the context of event-driven real-time systems, the verification of temporal properties is performed using the schedulability analysis based on the response time analysis. Each deployment choice has an essential impact on the validity and the quality of the system. However, the existing methodologies do not provide supportto guide the designer of applications in the exploration of the operational architectures space. The objective of this thesis is to develop techniques for analysis and automatic synthesis of a valid operational architecture optimized with respect to the system performances. Our proposition is dedicated to the exploration of architectures space considering at the same time the four degrees of freedom determined during the deployment phase, (i) the placement of functional elements on the computing and communication resources of the execution platform, (ii) the partitioning of function elements into real time tasks and data signals into messages, (iii) the priority assignment to system tasks and messages and (iv) the assignment of shared data protection mechanism for periodic real-time systems. We are mainly interested in meeting temporal constraints and memory capacity of the target platform. In addition, we are focusing on the optimization of end-to-end latency and memory consumption. The design space exploration approaches presented in this thesis are based on the MILP (Mixed Integer Linear programming) optimization technique and concern at the same time time-driven and data-driven applications. Unlike many earlier approaches providing a partial solution to the deployment problem, our methods consider the whole deployment problem. The proposed approaches in this thesis are evaluated using both synthetic and industrial applications.

Le souhait d’augmenter la part des énergies renouvelables dans le mix énergétique entraine une augmentation des parts des énergies volatiles et non pilotables, et rend donc l’équilibre offre-demande difficile à satisfaire. Une façon d’intégrer ces énergies dans le réseau électrique actuel est d’utiliser de petits moyens de production, de consommation et de stockage répartis sur tout le territoire pour compenser les sous ou sur productions. Afin que ces procédés puissent être intégrés dans le processus d’équilibre offre-demande, ils sont regroupés au sein d’une centrale virtuelle d’agrégation de flexibilité, qui est vue alors comme une centrale virtuelle. Comme pour tout autre moyen de production du réseau, il est nécessaire de déterminer son plan de production. Nous proposons dans un premier temps dans cette thèse une architecture et un mode de gestion pour une centrale d’agrégation composée de n’importe quel type de procédés. Dans un second temps, nous présentons des algorithmes permettant de calculer le plan de production des différents types de procédés respectant toutes leurs contraintes de fonctionnement. Et enfin, nous proposons des approches pour calculer le plan de production de la centrale d’agrégation dans le but de maximiser son gain financier en respectant les contraintes réseau. / The desire to increase the share of renewable energies in the energy mix leads to an increase inshare of volatile and non-controllable energy and makes it difficult to meet the supply-demand balance. A solution to manage anyway theses energies in the current electrical grid is to deploy new energy storage and demand response systems across the country to counter balance under or over production. In order to integrate all these energies systems to the supply and demand balance process, there are gathered together within a virtual flexibility aggregation power plant which is then seen as a virtual power plant. As for any other power plant, it is necessary to compute its production plan. Firstly, we propose in this PhD thesis an architecture and management method for an aggregation power plant composed of any type of energies systems. Then, we propose algorithms to compute the production plan of any types of energy systems satisfying all theirs constraints. Finally, we propose an approach to compute the production plan of the aggregation power plant in order to maximize its financial profit while complying with all the constraints of the grid.

Selon le rapport annuel de la croix rouge et du croissant rouge pour l’année 2006, le nombre de catastrophes, d’origine naturelle et humaine, a augmenté ces dernières décennies dans des proportions importantes. Ces catastrophes engendrent souvent un nombre de victimes important nécessitant des interventions urgentes. Face à une telle situation, les moyens sanitaires classiques et de routines se trouvent souvent dépassés, et par conséquent inefficaces pour absorber cet afflux massif de victimes. Ainsi, la mise en œuvre d’un système de gestion hospitalier conditionné par une optimisation des différentes ressources médicales est indispensable pour sauver le maximum de vies humaines. Dans ce contexte, nous proposons dans cette thèse, d’étudier le problème d’optimisation des ressources humaines et matérielles critiques à savoir, les chirurgiens et les salles opératoires en situation de crise. L’objectif est de traiter le maximum de victimes, autrement dit sauver le maximum de vies humaines. Notre étude comprend deux niveaux : (1) un niveau préparatoire qui consiste à dimensionner les ressources dans le cadre des exercices de simulation du plan blanc, et (2) un niveau opérationnel permettant d’optimiser l’ordonnancement des interventions dans les salles opératoires. Aussi, nous étudions l’impact de la mutualisation des ressources sur le nombre de victimes traitées. L’un des défis posés à la programmation opératoire en situation d’exception est l’aptitude à faire face aux perturbations. Dans ce cadre, nous abordons le problème réactif d’optimisation de l’ordonnancement des interventions dans les salles opératoires. Nous considérons diverses perturbations possibles telles : une durée opératoire qui dépasse la durée estimée, l’insertion d’une nouvelle victime dans le programme opératoire, et l’évolution du degré d’urgence d’une victime. Cette thèse est menée avec la collaboration de plusieurs structures sanitaires publiques en France et en Tunisie. Les résultats expérimentaux mettent en exergue l’apport de ces approches pour l’aide à la décision. / Disaster like terrorist attack, earthquake, and hurricane, often cause a high degree of damage. Thousands of people might be affected. The 2006’s annual report of the International Federation of Red Cross and Red Crescent Societies proves that the number of disasters increased during these last decades. In such situations, hospitals must be able to receive injured persons for medical and surgical treatments. For these reasons medical resources optimization of different is fundamental in human life save.In this context, we propose in this thesis, to study the optimization of human and material resources in relation with hospital management. We focus more precisely on critical resources: operating rooms and surgeons. The goal is to handle the maximum of victims and then to save the maximum of human lives. Our research consists of two phases: (1) Sizing critical resources during the preparedness phase of disaster management plan so called white plan. (2) Operational phase that provides the optimization of surgical acts scheduling in the operating rooms. Also, we study the impact of sharing resources on the number of treated victims. A disaster situation is characterized by different disruptions. In this setting, we approach a reactive problem for optimization of surgical acts scheduling in the operating rooms. We consider various possible disruptions: the overflow of assessed surgical care duration, the insertion of a new victim in the scheduling program, and the evolution of victim’s emergency level.This work is achieved with the collaboration of several public health institutions (hospitals, ministry, etc.) both in France and Tunisia. Empirical study shows that a substantial aid is proposed by using the proposed approaches.

Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces. / In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature.

Le transport fluvial de conteneurs constitue une activité économique importante qui suscite un intérêt grandissant de la part de scientifiques. Considéré comme durable et économique, le transport par barge a été identifié comme étant une alternative compétitive pour le transport de marchandises, en complément des modes traditionnels de transport, routier et ferroviaire. Néanmoins, les travaux de recherche en rapport avec la planification et le management du transport par barge, en particulier dans le contexte du transport intermodal, sont encore peu abondants. Le but de cette thèse est d’apporter une contribution dans ce domaine, par la proposition de modèles et de méthodes de planification et gestion avancées, dans le cadre d’un système d’aide à la décision pour le transport de conteneurs par barge développé pour accompagner les opérateurs de transport. La méthodologie proposée fait appel à des concepts et principes de gestion du revenu, des ressources et des services de transport pour la conception de plans de services réguliers avec horaires, au niveau tactique. Les opérateurs de transport peuvent ainsi offrir des plans de transport avec des services plus flexibles pour leurs clients, tout en assurant un meilleur niveau de fiabilité. Plus de demandes de transport pourront ainsi être satisfaites, avec globalement une plus grande satisfaction des chargeurs. Une originalité importante proposée par notre approche est l’utilisation de principes et techniques de gestion du revenu (segmentation du marché, classes tarifaires...) aussi bien au niveau opérationnel de la modélisation qu’au niveau tactique. Les problèmes d’optimisation sont formalisés sous forme de modèles de programmation linéaire mixte en nombres entiers (PLNE), implémentés et testés sous différentes configurations de réseaux de transport et différents scénarios de demandes, et ce pour chaque niveau de décision. Au niveau tactique, une nouvelle approche de résolution, combinant la recherche adaptative à voisinage large (ALNS) et la recherche taboue, est proposée pour résoudre des problèmes PLNE de grande taille. Une plateforme de simulation, qui intègre les niveaux tactique et opérationnel de prise de décision, est proposée pour la validation du système d’aide à la décision sous différentes configurations : différentes topologies du réseau physique, différents paramètres pour la gestion du revenu, différents degrés de précision caractérisant les prévisions de demande. Pour l’analyse des résultats numériques ainsi obtenus, plusieurs types d’indicateurs de performance sont proposés et utilisés. / Barge transportation is an important research topic that started to draw increasing scientific attention in the recent decade. Considered as sustainable, environment-friendly and economical, barge transportation has been identified as a competitive alternative for freight transportation, complementing the traditional road and rail modes. However, contributions related to barge transportation, especially in the context of intermodal transportation, are still scarce. The objective of this thesis is to contribute to fill this gap by proposing a reactive decision support system for freight intermodal barge transportation from the perspective of the carriers. The proposed system incorporates resource and revenue management concepts and principles to build the optimal set of scheduled services plans at the tactical level. Carriers may thus benefit from transportation plans offering increased flexibility and reliability. They could thus serve more demands and better satisfy customers. One novelty of the approach is the application of revenue management considerations (e.g., market segmentation and price differentiation) at both operational and tactical planning levels. The optimization problems are mathematically formalized and mixed integer linear programming (MILP) models are proposed, implemented and tested against various network settings and demand scenarios, for each decision level. At the tactical level, a new solution approach, combining adaptive large neighborhood search (ALNS) and Tabu search is designed to solve large scale MILP problems. An integrated simulation framework, including the tactical and the operational levels jointly, is proposed to validate the decision support system in different settings, in terms of physical network topology, revenue management parameters and accuracy degree of demand forecasts. To analyze the numerical results corresponding to the solutions of the optimization problems, several categories of performance indicators are proposed and used.

Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes. / This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.

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.