Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale. / This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem.

L’informatique joue un rôle de plus en plus prépondérant dans l’analyse et la compréhension des données biologiques. Dans cette thèse, nous présentons le problème de caractérisation multiple qui aborde, sous l’angle de l’optimisation combinatoire, la détection de souches bactériennes phytopathogènes. En effet, certaines bactéries sont responsables de pathologies sur une large gamme de cultures diminuant ainsi la valeur marchande des semences. Des tests de diagnostic peuvent être alors conçus et nécessitent l’identification de caractères observables discriminants. Nous avons développé plusieurs méthodes de résolution exactes (branch and bound et programmation linéaire) et approchées (métaheuristiques) afin de minimiser le nombre de caractères à traiter. Précisément, en considérant un sous-ensembles d’individus représentatifs de différents groupes, il s’agit d’établir pour chacun de ces groupes une caractérisation (sous forme de formule propositionnelle) permettant de distinguer les individus du groupe par rapport à ceux des autres groupes. Nous utilisons le terme (caractérisation multiple) pour rendre compte de l’aspect mutuel de ces discriminations au sens (un groupe versus le reste des groupes) et ce pour chaque groupe. Nos travaux ont été validés expérimentalement sur des jeux de données et une étude approfondie de la complexité de ce problème a été menée. / Computer science plays an increasingly important role in the analysis and understanding of biological data. In this thesis, we present the multiple characterization problem that addresses, as a combinatorial optimization problem, the detection of plant pathogenic bacterial strains. Indeed, some bacteria are responsible for diseases on a wide range of crops and decrease the market value of the seeds. Diagnostic tests can be designed and require the identification of discriminant observable characters. We have developed several exact methods (branch and bound, linear programming) and approximate (metaheuristics) to minimize the number of characters to deal with. Specifically, considering a subset of individuals representing different groups, the aim for each group is to find a characterization (as a propositional formula) to distinguish the individuals of the group compared to those of the other groups. We use the term “multiple characterization” to highlight the mutual aspect of theses discriminations in the sense “versus a group the other groups” and that for each group. Our work has been validated experimentally on data sets and an in-depth study of the problem’s complexity has been conducted.

Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement. Les heuristiques manquent d’une vue d’ensemble sur l’évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l’agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l’aide de l’apprentissage, l’agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s’échanger des informations, comme ils peuvent déclencher l’agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l’affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l’état de l’art. / We elaborate a multi-agent based optimization method for combinatorial optimization problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOMCOP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOMCOP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature

Cette thèse est une contribution aux travaux de recherche sur l’optimisation des problèmes du transport multimodal. Les principaux concepts clé de la multimodalité dans les réseaux du transport intermodal et l’état de l’art des travaux scientifique du domaine y sont présentés. Le problème de la localisation des terminaux du transport combiné est ensuite étudié. Nous proposons un algorithme génétique à codage mixte pour la résolution de ce problème et nous comparons nos résultats avec ceux de la littérature. Un ensemble de problèmes posés dans le cadre de notre travail sur le projet DCAS (Direct Cargo Axe Seine), porté par le Grand Port Maritime du Havre, y est décrit et modélisé par des outils de programmation mathématique. Ainsi, nous avons étudié le problème du transfert de navettes ferroviaires qui consiste à optimiser le transfert d’un ensemble de conteneurs entre des terminaux maritimes et un terminal multimodal. Ensuite, nous avons modélisé le problème d’ordonnancement des trains de grandes de lignes pour le placement sur les voies de la cour ferroviaire du terminal multimodal du Havre. Ces problèmes sont résolus en utilisant une approche combinée optimisation-simulation. Une première application est basée sur un algorithme génétique couplé avec la simulation multi agents pour l’affectation des voies aux trains. Une deuxième, consiste à optimiser la manutention des conteneurs lors d’un transbordement rail-rail en utilisant un algorithme de colonie de fourmis intégré dans le modèle de simulation et une stratégie de collaboration agents pour minimiser les temps d’attente des portiques et ainsi augmenter leurs productivités. / This thesis is a contribution to research on the optimization of multimodal transport problems. The main key concepts of multimodality in the intermodal transportation networks and the state of the art of scientific works in the field are presented. The intermodal terminal location problem is then studied. We propose a genetic algorithm with mixed encoding for solving this problem and we compare our results with those of literature. A set of problems in the framework of our work on the project DCAS (Direct Cargo Axe Seine), carried by the Grand Port Maritime du Havre, are described and modeled by mathematical programming tools. Thus, we studied the problem of the transfer of rail shuttles which is to optimize the transfer of a set of containers between maritime terminals and a multimodal terminal. We then modeled the scheduling problem of freight trains for placement on rail tracks. These problems are solved by using combined optimization simulation approaches. A first application is based on a genetic algorithm coupled with the multi agent’s simulation. A second is to optimize a rail-rail transshipment of containers using an ant colony algorithm embedded in the simulation model and an agent’s collaboration strategy to minimize waiting times and increase cranes productivity.541 ##‎$a@Optimization of multimodal transportation problems

La reconstruction phylogénétique est considérée comme un élément central de divers domaines comme l’écologie, la biologie et la physiologie moléculaire pour lesquels les relations généalogiques entre séquences d’espèces ou de gènes, représentées sous forme d’arbres, peuvent apporter des éclairages significatifs à la compréhension de phénomènes biologiques. Le problème de Maximum de Parcimonie est une approche importante pour résoudre la reconstruction phylogénétique en se basant sur un critère d’optimalité pour lequel l’arbre comprenant le moins de mutations est préféré. Dans cette thèse nous proposons différentes méthodes pour s’attaquer à la nature combinatoire de ce problème NP-complet. Premièrement, nous présentons un algorithme de Recuit Simulé compétitif qui nous a permis de trouver des solutions de meilleure qualité pour un ensemble de problèmes. Deuxièmement, nous proposons une nouvelle technique de Path-Relinking qui semble intéressante pour comparer des arbres mais pas pour trouver des solutions de meilleure qualité. Troisièmement, nous donnons le code d’une implantation sur GPU de la fonction objectif dont l’intérêt est de réduire le temps d’exécution de la recherche pour des instances dont la longueur des séquences est importante. Finalement, nous introduisons un prédicteur capable d’estimer le score optimum pour un vaste ensemble d’instances avec une très grande précision. / Phylogenetic reconstruction is considered a central underpinning of diverse fields like ecology, molecular biology and physiology where genealogical relationships of species or gene sequences represented as trees can provide the most meaningful insights into biology. Maximum Parsimony (MP) is an important approach to solve the phylogenetic reconstruction based on an optimality criterion under which the tree that minimizes the total number of genetic transformations is preferred. In this thesis we propose different methods to cope with the combinatorial nature of this NP-complete problem. First we present a competitive Simulated Annealing algorithm which helped us find trees of better parsimony score than the ones that were known for a set of instances. Second, we propose a Path-Relinking technique that appears to be suitable for tree comparison but not for finding trees of better quality. Third, we give a GPU implementation of the objective function of the problem that can reduce the runtime for instances that have an important number of residues per taxon. Finally, we introduce a predictor that is able to estimate the best parsimony score of a huge set of instances with a high accuracy.

Supply chain optimization is one of the key components for the effective management of a company with a complex manufacturing process and distribution network. Companies with a global presence in particular are motivated to optimize their distribution plans in order to keep their operating costs low and competitive. Changing condition in the global market and volatile energy prices increase the need for an automatic decision and optimization tool. In recent years, many techniques and applications have been proposed to address the problem of supply chain optimization. However, such techniques are often too problemspecific or too knowledge-intensive to be implemented as in-expensive, and easy-to-use computer system. The effort required to implement an optimization system for a new instance of the problem appears to be quite significant. The development process necessitates the involvement of expert personnel and the level of automation is low. The aim of this project is to develop a set of strategies capable of increasing the level of automation when developing a new optimization system. An increased level of automation is achieved by focusing on three areas: multi-objective optimization, optimization algorithm usability, and optimization model design. A literature review highlighted the great level of interest for the problem of multiobjective optimization in the research community. However, the review emphasized a lack of standardization in the area and insufficient understanding of the relationship between multi-objective strategies and problems. Experts in the area of optimization and artificial intelligence are interested in improving the usability of the most recent optimization algorithms. They stated the concern that the large number of variants and parameters, which characterizes such algorithms, affect their potential applicability in real-world environments. Such characteristics are seen as the root cause for the low success of the most recent optimization algorithms in industrial applications. Crucial task for the development of an optimization system is the design of the optimization model. Such task is one of the most complex in the development process, however, it is still performed mostly manually. The importance and the complexity of the task strongly suggest the development of tools to aid the design of optimization models. In order to address such challenges, first the problem of multi-objective optimization is considered and the most widely adopted techniques to solve it are identified. Such techniques are analyzed and described in details to increase the level of standardization in the area. Empirical evidences are highlighted to suggest what type of relationship exists between strategies and problem instances. Regarding the optimization algorithm, a classification method is proposed to improve its usability and computational requirement by automatically tuning one of its key parameters, the termination condition. The algorithm understands the problem complexity and automatically assigns the best termination condition to minimize runtime. The runtime of the optimization system has been reduced by more than 60%. Arguably, the usability of the algorithm has been improved as well, as one of the key configuration tasks can now be completed automatically. Finally, a system is presented to aid the definition of the optimization model through regression analysis. The purpose of the method is to gather as much knowledge about the problem as possible so that the task of the optimization model definition requires a lower user involvement. The application of the proposed algorithm is estimated that could have saved almost 1000 man-weeks to complete the project. The developed strategies have been applied to the problem of Caterpillar’s global supply chain optimization. This thesis describes also the process of developing an optimization system for Caterpillar and highlights the challenges and research opportunities identified while undertaking this work. This thesis describes the optimization model designed for Caterpillar’s supply chain and the implementation details of the Ant Colony System, the algorithm selected to optimize the supply chain. The system is now used to design the distribution plans of more than 7,000 products. The system improved Caterpillar’s marginal profit on such products by a factor of 4.6% on average.

Au cours de cette thèse, l'exploration de l'espace de solutions par des métaheuristiques est abordée. Les métaheuristiques sont des méthodes d'optimisation utilisées pour résoudre des problèmes NP-difficile. Elles explorent aléatoirement l'espace de recherche pour trouver les meilleures solutions. Dans un premier temps, l'ensemble des solutions est modélisé par un espace unidimensionnel par une Méthode de Conversion de l'Espace de recherche (MCE). Des métriques sont proposées pour évaluer l'exploration de l'espace de recherche par une métaheuristique en identifiant les zones explorées et inexplorées. Ces métriques sont utilisées pour orienter l'exploration de l'espace de recherche d'une méthode d'optimisation.La convergence est améliorée en accentuant le recherche dans les zones explorées. Pour sortir des minimums locaux, l'exploration est diversifiée en la dirigeant vers les zones inexplorées. En associant l'exploration du voisinage des solutions et ces métriques cartographiques, il est possible d'améliorer les performances des métaheuristiques. Plusieurs algorithmes mono-objectifs et multiobjectifs sont implémentés en version classique, hybridé par la recherche locale et par la MCE. Le Flexible Job Shop Problem (FJSP) est utilisé comme problème de référence. Les expérimentations avec les algorithmes hybridés montrent une amélioration des performances / In this thesis, the solution space exploration by the metaheuristic is developed. The metaheuristics optimization methods are used to solve NP-hard problems. They explore randomly the search space to look for the best solutions. In a first step, the solution set is modeled by a one-dimensional space by a Mapping Method (MaM). Metrics are proposed to evaluate the search space exploration by a metaheuristic, identifying the explored and unexplored zones. These metrics are used to guide the search space exploration of an optimization method. The convergence is improved by emphasizing the research in the zones explored. To get out local minima, the exploration is diversified by pointing it towards the unexplored zones. Combining the neighbour discovery of the solutions and these mapping metrics, it is possible to improve the performance of metaheuristics. Several single-objective and multi-objective algorithms are implemented in the classic version, hybridized with local search and MaM. The Flexible Job Shop Problem (FJSP) is used as a reference problem. The experimentations with hybridized algorithms show performance improved

Constructing the genomic median of several given genomes is crucial in developing evolutionary trees, since the genomic median provides an estimate for the ordering of the genes in a common ancestor of the given genomes. This is due to the fact that the content of DNA molecules is often similar, but the difference is mainly in the order in which the genes appear in various genomes. The mutations that affect this ordering are called genome rearrangements, and many structural differences between genomes can be studied using genome rearrangements. In this thesis our main focus is on applying combinatorial optimization techniques to genomic median problems, with particular emphasis on the breakpoint distance as a measure of the difference between two genomes. We will study different variations of the breakpoint median problem from signed to unsigned, unichromosomal to multichromosomal, and linear to circular to mixed. We show how these median problems can be formulated in terms of problems in combinatorial optimization, and take advantage of well-known combinatorial optimization techniques and apply these powerful methods to study various median problems. Some of these median problems are polynomial and many are NP-hard. We find efficient algorithms and approximation methods for median problems based on well-known combinatorial optimization structures. The focus is on algorithmic and combinatorial aspects of genomic medians, and how they can be utilized to obtain optimal median solutions.

Le Design computationnel de protéines, en anglais « Computational Protein Design » (CPD), est un champ derecherche récent qui vise à fournir des outils de prédiction pour compléter l'ingénierie des protéines. En effet,outre la compréhension théorique des propriétés physico-chimiques fondamentales et fonctionnelles desprotéines, l’ingénierie des protéines a d’importantes applications dans un large éventail de domaines, y comprisdans la biomédecine, la biotechnologie, la nanobiotechnologie et la conception de composés respectueux del’environnement. Le CPD cherche ainsi à accélérer le design de protéines dotées des propriétés désirées enpermettant le traitement d’espaces de séquences de large taille tout en limitant les coûts financier et humain auniveau expérimental.Pour atteindre cet objectif, le CPD requière trois ingrédients conçus de manière appropriée: 1) une modélisationréaliste du système à remodeler; 2) une définition précise des fonctions objectives permettant de caractériser lafonction biochimique ou la propriété physico-chimique cible; 3) et enfin des méthodes d'optimisation efficacespour gérer de grandes tailles de combinatoire.Dans cette thèse, nous avons abordé le CPD avec une attention particulière portée sur l’optimisationcombinatoire. Dans une première série d'études, nous avons appliqué pour la première fois les méthodesd'optimisation de réseaux de fonctions de coût à la résolution de problèmes de CPD. Nous avons constaté qu’encomparaison des autres méthodes existantes, nos approches apportent une accélération du temps de calcul parplusieurs ordres de grandeur sur un large éventail de cas réels de CPD comprenant le design de la stabilité deprotéines ainsi que de complexes protéine-protéine et protéine-ligand. Un critère pour définir l'espace demutations des résidus a également été introduit afin de biaiser les séquences vers celles attendues par uneévolution naturelle en prenant en compte des propriétés structurales des acides aminés. Les méthodesdéveloppées ont été intégrées dans un logiciel dédié au CPD afin de les rendre plus facilement accessibles à lacommunauté scientifique. / Computational Protein Design (CPD) is a very young research field which aims at providing predictive tools to complementprotein engineering. Indeed, in addition to the theoretical understanding of fundamental properties and function of proteins,protein engineering has important applications in a broad range of fields, including biomedical applications, biotechnology,nanobiotechnology and the design of green reagents. CPD seeks at accelerating the design of proteins with wanted propertiesby enabling the exploration of larger sequence space while limiting the financial and human costs at experimental level.To succeed this endeavor, CPD requires three ingredients to be appropriately conceived: 1) a realistic modeling of the designsystem; 2) an accurate definition of objective functions for the target biochemical function or physico-chemical property; 3)and finally an efficient optimization framework to handle large combinatorial sizes.In this thesis, we addressed CPD problems with a special focus on combinatorial optimization. In a first series of studies, weapplied for the first time the Cost Function Network optimization framework to solve CPD problems and found that incomparison to other existing methods, it brings several orders of magnitude speedup on a wide range of real CPD instancesthat include the stability design of proteins, protein-protein and protein-ligand complexes. A tailored criterion to define themutation space of residues was also introduced in order to constrain output sequences to those expected by natural evolutionthrough the integration of some structural properties of amino acids in the protein environment. The developed methods werefinally integrated into a CPD-dedicated software in order to facilitate its accessibility to the scientific community.

Dans le cadre de l’aide à l’analyse de dialogues, un corpus de dialogues peut être représenté par un ensemble de tableaux d’annotations encodant les différents énoncés des dialogues. Afin d’identifier des schémas dialogiques mis en oeuvre fréquemment, nous définissons une méthodologie en deux étapes : extraction de motifs récurrents, puis partitionnement de ces motifs en classes homogènes constituant ces régularités. Deux méthodes sont développées afin de réaliser l’extraction de motifs récurrents : LPCADC et SABRE. La première est une adaptation d’un algorithme de programmation dynamique tandis que la seconde est issue d’une modélisation formelle du problème d’extraction d’alignements locaux dans un couple de tableaux d’annotations.Le partitionnement de motifs récurrents est réalisé par diverses heuristiques de la littérature ainsi que deux formulations originales du problème de K-partitionnement sous la forme de programmes linéaires en nombres entiers. Lors d’une étude polyèdrale, nous caractérisons des facettes d’un polyèdre associé à ces formulations (notamment les inégalités de 2-partitions, les inégalités 2-chorded cycles et les inégalités de clique généralisées). Ces résultats théoriques permettent la mise en place d’un algorithme de plans coupants résolvant efficacement le problème.Nous développons le logiciel d’aide à la décision VIESA, mettant en oeuvre ces différentes méthodes et permettant leur évaluation au cours de deux expérimentations réalisées par un expert psychologue. Des régularités correspondant à des stratégies dialogiques que des extractions manuelles n’avaient pas permis d’obtenir sont ainsi identifiées. / In the context of dialogue analysis, a corpus of dialogues can be represented as a set of arrays of annotations encoding the dialogue utterances. In order to identify the frequently used dialogue schemes, we design a two-step methodology in which recurrent patterns are first extracted and then partitioned into homogenous classes constituting the regularities. Two methods are developed to extract recurrent patterns: LPCA-DC and SABRE. The former is an adaptation of a dynamic programming algorithm whereas the latter is obtained from a formal modeling of the extraction of local alignment problem in annotations arrays.The partitioning of recurrent patterns is realised using various heuristics from the literature as well as two original formulations of the K-partitioning problem in the form of mixed integer linear programs. Throughout a polyhedral study of a polyhedron associated to these formulations, facets are characterized (in particular: 2-chorded cycle inequalities, 2-partition inequalities and general clique inequalities). These theoretical results allow the establishment of an efficient cutting plane algorithm.We developed a decision support software called VIESA which implements these different methods and allows their evaluation during two experiments realised by a psychologist. Thus, regularities corresponding to dialogical strategies that previous manual extractions failed to identify are obtained.