Search

The domain of energy management involves many combinatorial optimization problems known to be computationally hard. The emergence of quantum computers suggests new approaches for these problems. For near-future machines particularly promising are variational quantum heuristics such as QAOA that can leverage the computational power of the imperfect quantum hardware. We explore the potential of variational quantum algorithms for optimization problems issued from the field of "smart charging"}of electrical vehicles. We consider two problems inspired by real-world usecases. In the first problem, modeled as Max-K-Cut, we search to schedule a set of prioritized charges on several stations while minimizing the weighted completion time. In the second problem, modeled as Maximum Independent Set, we aim to maximize the number of satisfied charge demands on a single station while respecting the conflicts between demands. For both problems, we develop an experimental protocol specifying the encoding step and the parameter optimization routine. Our numerical experiments confirm the interest of quantum heuristics for these problems as well as the quality of our experimental protocol. In order to extend the applicability of quantum heuristics beyond QUBO we introduce a new hybrid approach that integrates quantum routines in the classical Branch & Price algorithm for large integer linear programs. We test this approach on a smart charging problem that is modeled as graph coloring problem. Our computational results affirm the potential of the hybrid approach while revealing the considerable dependence of the performance gain on the particular instance of the problem. Important components of variational algorithms can be represented as ZX-diagrams. We demonstrate how the rewriting rules of ZX-calculus can be used to derive the analytical formula for the mean energy of a general Ising model in a QAOA of depth 1 state. Furthermore, we contribute to the theoretical exploration of variational algorithms by extending the ZX-calculus with addition and differentiation of ZX-diagrams. Our inductive procedure for the addition is fully diagrammatic. For the differentiation we suggest two approaches. The first approach is inductive, it leverages our procedure for addition to explicitly represent the product rules. The second approach is resumed in two formulas derived from the factored form of parameterized diagrams.; Le domaine du management de l'énergie implique de nombreux problèmes d'optimisation combinatoire connus pour être difficiles. L'émergence des ordinateurs quantiques suggère de nouvelles approches pour ces problèmes. Pour les machines du futur proche, les heuristiques quantiques variationnelles telles que QAOA, qui peuvent tirer parti de la puissance de calcul des ordinateurs quantiques imparfaits, sont particulièrement prometteuses. Nous explorons le potentiel des algorithmes quantiques variationnels pour des problèmes d'optimisation issus du domaine de "smart charging" des véhicules électriques. Nous considérons deux problèmes inspirés de cas d'utilisation réels. Dans le premier problème, modélisé par Max-K-Cut, nous cherchons à planifier un ensemble de charges avec priorités sur plusieurs stations tout en minimisant le temps de completion pondéré. Dans le deuxième problème, modélisé par Maximum Independent Set, nous cherchons à maximiser le nombre de demandes de charge satisfaites sur une seule station tout en respectant les conflits entre les demandes. Pour les deux problèmes, nous développons un protocole expérimental spécifiant l'encodage et la routine d'optimisation des paramètres. Nos expériences numériques confirment l'intérêt des heuristiques quantiques pour ces problèmes ainsi que la qualité de notre protocole expérimental. Afin d'étendre l'applicabilité des heuristiques quantiques au-delà de QUBO, nous introduisons une nouvelle approche hybride qui intègre des routines quantiques dans l'algorithme classique de Branch & Price pour les programmes linéaires en nombres entiers. Nous testons cette approche sur un problème de smart charging qui se modélise comme problème de coloration de graphe. Nos résultats numériques affirment le potentiel de l'approche hybride tout en révélant la dépendance considérable du gain de performance sur l'instance particulière du problème. Les parties importants des algorithmes variationnels peuvent être représentés sous forme de diagrammes ZX. Nous démontrons comment les règles de réécriture du ZX-calculus peuvent être utilisées pour dériver la formule analytique de l'énergie moyenne d'un modèle d'Ising dans un état QAOA with depth 1. De plus, nous contribuons à l'exploration théorique des algorithmes variationnels en étendant le ZX-calcul avec addition et différenciation de ZX-diagrammes. Notre procédure inductive pour l'addition est entièrement graphique. Pour la différenciation, nous suggérons deux approches. La première approche est inductive, elle s'appuie sur notre procédure d'addition pour représenter explicitement les règles du produit. La deuxième approche est résumée dans deux formules qui sont dérivées de la forme factorisée des diagrammes paramétrés.

International audience; Dans ce papier, on présente un outil, MS-Builder, qui génère des certificats pour le problème Max-SAT, en appelant itérativement un oracle SAT pour générer une réfutation par résolution de la formule qui est ensuite rendue valide pour Max-SAT et appliquée sur la formule. Ce procédé est répété jusqu'à ce que la formule restante devienne satisfiable. On propose également un outil, MS-Checker, capable de vérifier les certificats Max-SAT basés sur l'application de règles d'inférence Max-SAT. Cet article résume les travaux publiés à la conférence SAT 2021 [4].

In this thesis, we are interested in multi-objective combinatorial optimization, and in particular in evolutionary algorithms based on decomposition. This type of approaches consists in decomposing the original multi-objective problem into multiple single-objective sub-problems that are then solved cooperatively. In this context, we consider the design and the analysis of new algorithmic components contributing to the establishment of the foundations of an optimization framework based on decomposition for multi-objective combinatorial problems known as "black box", i.e., for which the analytical form of the objective functions is not available to the solving algorithm. First of all, we investigate the key components for a better distribution of the computational efforts during the optimization process. To this end, we study the joint impact of the population size and of the number of solutions generated at each iteration, while proposing different strategies for selecting one ore multiple sub-problem(s) to be optimized at each stage. We then study different mechanisms allowing to escape from local optima. They are inspired by techniques from single-objective optimization, and we show they can significantly improve the convergence profile of the considered approaches. Finally, we consider the context of expensive optimization, where the evaluation of each solution is particularly intensive in terms of computational resources. This hence drastically restrict the budget allocated to the optimization process. As such, we investigate new components based on combinatorial meta-models, and we consider their integration within decomposition-based multi-objective evolutionary approaches.; Dans cette thèse, nous nous intéressons à l'optimisation combinatoire multi-objectif, et en particulier aux algorithmes évolutionnaires à base de décomposition. Ce type d'approches consiste à décomposer le problème multi-objectif original en plusieurs sous-problèmes mono-objectifs, qui sont alors résolus de façon coopérative. Dans ce cadre, nous considérons la conception et l'analyse de nouveaux composants algorithmiques contribuant à la mise en place des fondations d'un framework d'optimisation à base de décomposition pour les problèmes combinatoires multi-objectifs dits "boîte-noire", pour lesquels la forme analytique des fonctions objectif n'est pas connue de l'algorithme de résolution. Tout d'abord, nous étudions les éléments clés pour une meilleure répartition des efforts de calculs tout au long du processus d'optimisation. Pour cela, nous étudions l'impact conjoint de la taille de la population et du nombre de solutions générées par itération, tout en proposant différentes stratégies de sélection du ou des sous-problèmes à optimiser à chaque étape. Nous étudions ensuite différents mécanismes permettant de s'échapper des optima locaux. Ceux-ci s'inspirent de techniques issues de l'optimisation mono-objectif et permettent d'améliorer considérablement le profil de convergence des approches considérées. Nous nous plaçons pour finir dans un contexte d'optimisation coûteuse, où l'évaluation de chaque solution s'avère particulièrement gourmande en temps de calcul, ce qui limite considérablement le budget alloué à l'optimisation. Pour cela, nous étudions de nouveaux composants s'appuyant sur des méta-modèles combinatoires, et nous considérons leur intégration au sein d'approches évolutionnaires multi-objectifs basées sur la décomposition.

Quantum machine provide an opportunity to revolutionizing many fields, especially in combinatorial algorithms. In this internship, we propose to assess the performance of existing (and published) algorithms and clarify the opportunities ofquantum algorithms. In a first step, we use a search algorithm on an unstructured database published by Lov Grover (1996) and two other algorithms inspired by the Grover algorithm dealing with the satisfiability problem on a logical formulas and search for elements in an array. The second part present quantum algorithms necessary to do combinatorial optimization, such as the sumation and minimization. Finally, we experimentally solve the problem of vertex cover and traveling salesman problem.; L’arrivée des machines quantiques risque de révolutionner de nombreux domaines, en particulier celui des algorithmes combinatoires. Nous proposons dans ce stage d’évaluer la performance des algorithmes existants (et publiés) et d’éclairerles opportunités des algorithmes quantiques. Dans un premier temps, nous allons aborder l’algorithme de recherche dans une base non structurée de Lov Grover (1996) ainsi que deux autres algorithmes inspirés de l’algorithme de Grover traitant le problème de satisfiabilité d’une formule logique et la recherche d’éléments dans un tableau. La seconde partie présente des algorithmes quantiques nécessaires pour faire de l’optimisation combinatoire, tels que la somme ou encore la minimisation. Enfin,nous abordons le problème de la couverture d’arêtes (Vertex Cover - VC) et voyageur de commerce (Traveling Salesman Problem - TSP).

In many decision making problems encountered in practice, there is a need to reason at different abstraction levels. This is the case for multi-robot exploration missions, which involve decisions on how exploration tasks are shared between robots, on how these tasks are successively realized by each robot, and on how robots moves are coordinated so as to avoid collisions or to maintain communication links. This is also the case for the management of a constellation of Earth observation satellites, for which decisions must be made concerning how candidate observation tasks are shared between satellites, concerning how each satellite realizes the set of observation tasks allocated to it, and concerning the basic commands that must be sent to instruments for achieving the acquisition plan.This is again the case for the mapping of functions onto an embedded architecture, with first a decision concerning the allocation of functions onto real-time computation units, then a decision concerning the scheduling of functions on each unit, and last a decision on the routing of data exchanged between functions inside an available inter-units network. From a general point of view, such applications require being able to deal with different decision levels covering task allocation and task scheduling over ressources. Additionnally, each task involved must also sometimes be decomposed into subtasks, as in the case of a function computation task which is decomposed into one subtask for reading the set of data used by the function, one subtask for actually performing the computation, and one subtask for writing the result of the computation in a dedicated buffer. Additionnally, the constraints of the decision making problem to solve can be modeled using different abstraction levels. For instance, in multi-robot exploration, there exist constraints on the energy available for each robot all along the mission. At the time of task sharing between robots, it is not possible for combinatorial reasons to consider a complex dynamic model linking the level of energy available to the instantaneous power consumption. Instead, a simpler model might be used, in which a fixed amount of energy is consumed by each task. The complex energy model can be considered again once tasks have been allocated to robots and once robot moves have been synthesized. Similarly, for Earth observing satellites, it is possible to consider a fixed duration between the realization of two successive activities before considering finer a model taking into account the kinematics of satellites and the coordinates of images to be realized. The goal of this thesis is to define new models and algorithms for handling such hierarchical decision making problems., Dans de nombreuses applications qui présentent un problème de décision ou d'optimisation combinatoire, il est utile de raisonner à différents niveaux d'abstraction. C'est par exemple le cas pour des missions d'exploration multi-robots, où l'on peut s'intéresser premièrement à la répartition de tâches d'exploration entre différents robots, puis à la manière dont chaque robot enchaîne les tâches qui lui sont allouées, et enfin à la décomposition de ces enchaînements de tâches sous la forme de déplacements à coordonner pour éviter des collisions. D'un point de vue général, il est nécessaire dans ce type d'application de considérer différents niveaux de décision couvrant allocation des tâches sur des ressources et ordonnancement des tâches sur ces mêmes ressources. Chaque tâche à considérer peut de plus se décomposer en plusieurs sous-tâches qui doivent toutes être réalisées pour que la tâche parente le soit. Plusieurs alternatives de décomposition peuvent être considérées dans ce cas. Finalement, les contraintes des problèmes de décision à résoudre peuvent être représentées avec différents niveaux d'abstraction. La thèse s'intéresse à la définition de modèles et d'algorithmes de décision utilisables pour gérer ces problématiques de décision hiérarchique. Plus précisément, les contributions de la thèse consistent tout d’abord en la définition d’un modèle générique pour les problèmes d’ordonnancement hiérarchique, ainsi que la définition d’un cadre générique permettant de décomposer un tel problème en plusieurs couches. Ensuite, lorsque le problème est découpé en plusieurs couches, deux stratégies d’interaction sont proposées entre les couches, une première inspirée des modèles de substitution et la seconde inspirée des décompositions logiques de Benders. Des expérimentations menées sur l’application de déploiement multirobot montrent l’efficacité des approches proposées.

As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, multi-objective evolutionary algorithms could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii) Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.; Comme ils requièrent généralement des capacités de calcul importantes pour explorer de grandes régions de l'espace de recherche dans la résolution de problèmes réels et complexes, les algorithmes évolutionnaires multi-objectifs peuvent bénéficier des nouvelles architectures de calcul haute performance. Ainsi, des approches parallèles ont été proposées à la fois pour réduire leur temps d'exécution et améliorer la qualité des solutions fournies. Bien que des progrès significatifs aient été réalisés ces dernières années dans la conception et l'amélioration de modèles parallèles pour les algorithmes évolutionnaires, la plupart de ces modèles ont une extensibilité limitée et des difficultés à manipuler des problèmes variés. Résoudre efficacement un problème combinatoire multi-objectifs sur une architecture de calcul haute performance demeure encore un défi aujourd'hui.Dans cette thèse, des mécanismes sont proposés au sein d'un nouveau modèle parallèle pour exploiter de multiples unités de calcul dans la résolution de problèmes multi-objectifs. L'approche générale reprend les principes des modèles en îles avec une division de l'espace objectif qui repose sur une méthode de regroupement. Les principales caractéristiques du modèle sont (i) la vue globale donnée à l'île organisatrice pour atteindre une meilleure distribution des solutions (ii) des communications asynchrones pour réduire les surcoûts du parallélisme (iii) des îles témoins pour accroitre la diversification (iv) une phase de recherche locale pour améliorer la qualité des solutions. Une étude expérimentale minutieuse est effectuée afin d'évaluer les performances de l'approche et plus particulièrement de chaque composante dans la résolution de deux problèmes combinatoires classiques, le problème de voyageur de commerce multi-objectifs et le problème d'affectation quadratique multi-objectifs. L'extensibilité et la qualité des solutions sont analysées comparativement aux modèles parallèles de la littérature.

As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, multi-objective evolutionary algorithms could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii) Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models., Comme ils requièrent généralement des capacités de calcul importantes pour explorer de grandes régions de l'espace de recherche dans la résolution de problèmes réels et complexes, les algorithmes évolutionnaires multi-objectifs peuvent bénéficier des nouvelles architectures de calcul haute performance. Ainsi, des approches parallèles ont été proposées à la fois pour réduire leur temps d'exécution et améliorer la qualité des solutions fournies. Bien que des progrès significatifs aient été réalisés ces dernières années dans la conception et l'amélioration de modèles parallèles pour les algorithmes évolutionnaires, la plupart de ces modèles ont une extensibilité limitée et des difficultés à manipuler des problèmes variés. Résoudre efficacement un problème combinatoire multi-objectifs sur une architecture de calcul haute performance demeure encore un défi aujourd'hui.Dans cette thèse, des mécanismes sont proposés au sein d'un nouveau modèle parallèle pour exploiter de multiples unités de calcul dans la résolution de problèmes multi-objectifs. L'approche générale reprend les principes des modèles en îles avec une division de l'espace objectif qui repose sur une méthode de regroupement. Les principales caractéristiques du modèle sont (i) la vue globale donnée à l'île organisatrice pour atteindre une meilleure distribution des solutions (ii) des communications asynchrones pour réduire les surcoûts du parallélisme (iii) des îles témoins pour accroitre la diversification (iv) une phase de recherche locale pour améliorer la qualité des solutions. Une étude expérimentale minutieuse est effectuée afin d'évaluer les performances de l'approche et plus particulièrement de chaque composante dans la résolution de deux problèmes combinatoires classiques, le problème de voyageur de commerce multi-objectifs et le problème d'affectation quadratique multi-objectifs. L'extensibilité et la qualité des solutions sont analysées comparativement aux modèles parallèles de la littérature.

In a sequencing experiment, we can only ``read'' small fragments (called reads) of DNA due to physical limitations, whose location on the genome is unknown.De novo assembly aims to put them together to retrieve the full DNA sequence, like a jigsaw puzzle.The OLC approach computes pairwise Overlaps between reads to find their Layout, and then derive a Consensus sequence.The layout can be cast as an instance of the Seriation combinatorial problem, seeking to reorder a set of elements based on their pairwise similarity, such that similar elements are nearby.In a noiseless setting, a spectral method can solve Seriation efficiently.Still, it often fails on noisy, real DNA data.Notably, assembly is challenged by repeated genomic regions (called repeats) causing distant fragments to be similar.Most assembly engines follow hierarchical, greedy schemes, including modules dedicated to detect and disambiguate repeats while constructing the output sequence.We explore a simpler approach using Seriation to lay out all reads at once.Our first contribution is to show that the spectral method can be seamlessly integrated in an OLC framework, yielding competitive results compared to standard methods on real data.However, due to repeats, the method can only find fragmented assemblies (with a few large assembled fragments), i.e., it does not succeed to layout all the reads together at once.In our second contribution, we extend the spectral method using a multidimensional spectral embedding.It provides a unifying framework for seriation and circular seriation, a variant searching for a cyclic ordering of the data.This method significantly improves the robustness of the original algorithm on noisy data, and yields single-contig assembly of bacterial genomes.As a third contribution, we introduce the Robust Seriation framework, formalizing the task of seriation on corrupted data. We outline the relation between (robust) seriation and other combinatorial problems, particularly for stylized matrices modeling DNA sequencing data. We propose dedicated algorithms that experimentally improve robustness on synthetic and real data, although they turn out to be more sensitive than the method constituting our second contribution.In a fourth contribution, we introduce the problem of Seriation with Duplications, which is motivated by the application of assembling cancer genome from spatial conformation (Hi-C) data.We propose an alternated minimization algorithm that can utilize methods designed to solve Robust Seriation, and evaluate it on toy data.; Les technologies de séquençage d'ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome.L'assemblage de novo vise à reconstituer une séquence d'ADN entière en mettant ces fragments bout-à-bout, tel un puzzle.Dans l'approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus.Le réarrangement peut s'écrire comme un problème combinatoire de sériation, où l'on réordonne des éléments comparable entre eux, de sorte que deux éléments adjacents sont similaires.Ce problème est résolu efficacement par un algorithme spectral en l'absence de bruit, mais il en va autrement des données génomiques réelles.En particulier, des régions du génome sont similaires bien qu'éloignées (séquences répétées), rendant l'assemblage problématique.Les méthodes d'assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées.Nous proposons ici une approche épurée où l'on réarrange tous les fragments "d'un coup" via la résolution de sériation.Notre première contribution montre que l'emploi de la méthode spectrale pour le réarrangement s'intègre parfaitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard.Cependant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d'une).La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances,englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié.Ce prolongement rend l'algorithme robuste au bruit et résout le problème de fragmentation de l'assemblage précédent.Notre troisième contribution formalise la sériation robuste, où l'on souhaite réordonner des données bruitées. Nous décrivons des liens avec d'autres problèmes combinatoires, en particulier pour des matrices modélisant les données réelles d'ADN. Nous proposons des algorithmes adaptés, améliorant expérimentalement la robustesse sur données synthétiques et réelles, bien que moins clairement que la deuxième contribution.La quatrième contribution présente le problème de sériation avec duplication, motivé par l'assemblage de génomes cancéreux via des données de conformation spatiale, que nous tentons de résoudre avec un algorithme de projections alternées fondé en partie sur les méthodes de sériation robuste, sur données synthétiques.

In a sequencing experiment, we can only “read” small fragments (reads) of DNA due to physical limitations, whose location on the genome is unknown. De novo assembly aims to put them together to retrieve the full DNA sequence, like a jigsaw puzzle. The OLC approach computes pairwise Overlaps between reads to find their Layout, and then derive a Consensus sequence. The layout can be cast as an instance of the Seriation combinatorial problem, seeking to reorder a set of elements based on their pairwise similarity, such that similar elements are nearby. In a noiseless setting, a spectral method can solve Seriation efficiently. Still, it often fails on noisy, real DNA data. Notably, assembly is challenged by repeated genomic regions (repeats) causing distant fragments to be similar. Most assembly engines follow hierarchical, greedy schemes, including modules dedicated to detect and disambiguate repeats while constructing the output sequence. We explore a simpler approach using Seriation to lay out all reads at once. Our first contribution is to show that the spectral method can be seamlessly integrated in an OLC framework, yielding competitive results compared to standard methods on real data. However, due to repeats, the method can only find fragmented assemblies (with a few large assembled fragments), i.e., it does not succeed to lay- out all the reads together at once. In our second contribution, we extend the spectral method using a multidimensional spectral embedding. It provides a unifying framework for seriation and circular seriation, a variant searching for a cyclic ordering of the data. This method significantly improves the robustness of the original algorithm on noisy data, and yields single contig assembly of bacterial genomes. As a third contribution, we introduce the Robust Seriation framework, formalizing the task of seriation on corrupted data. We outline the relation between (robust) seriation and other combinatorial problems, particularly for stylized matrices modeling DNA sequencing data. We pro- pose dedicated algorithms that experimentally improve robustness on synthetic and real data, although they turn out to be more sensitive than the method constituting our second contribution. In a fourth contribution, we introduce the problem of Seriation with Duplications, which is motivated by the application of assembling cancer genome from spatial conformation (Hi-C) data. We propose an alternated minimization algorithm that can utilize methods designed to solve Robust Seriation, and evaluate it on toy data., Les technologies de séquençage d’ADN ne permettent de lire que de courts fragments, dont on ignore la position sur le génome. L’assemblage de novo vise à reconstituer une séquence d’ADN entière en mettant ces fragments bout-à-bout, tel un puzzle. Dans l’approche OLC (overlap-layout-consensus), on calcule le chevauchement entre fragments afin de les disposer en ordre (réarrangement), puis extraire une séquence consensus. Le réarrangement peut s’écrire comme un problème combinatoire de sériation, où l’on réordonne des éléments comparables entre eux, de sorte que deux éléments adjacents sont similaires. Ce problème est résolu efficacement par un algorithme spectral en l’absence de bruit, mais il en va autrement des données génomiques réelles. En particulier, des régions du génome sont similaires bien qu’éloignées (séquences répétées), rendant l’assemblage problématique. Les méthodes d’assemblage emploient des algorithmes hiérarchiques et gloutons pour désambiguïser les séquences répétées. Nous proposons ici une approche épurée où l’on réarrange tous les fragments « d’un coup »via la résolution de sériation. Notre première contribution montre que l’emploi de la méthode spectrale pour le réarrangement s’intègre par- faitement dans le schéma OLC, produisant des résultats de qualité semblable aux méthodes standard. Ce- pendant, du fait des séquences répétées, cette méthode produit des assemblages fragmentés (typiquement en quelques sous-séquences au lieu d’une). La deuxième contribution est un prolongement de la méthode spectrale lié à la réduction de dimension sous conservation de distances, englobant les problèmes de sériation et de sériation circulaire (une variante où les éléments peuvent être ordonnés selon un cycle) dans un cadre unifié. Ce prolongement rend l’algorithme robuste au bruit et résout le problème de fragmentation de l’assemblage précédent. Notre troisième contribution formalise la sériation robuste, où l’on souhaite réordonner des données bruitées. Nous décrivons des liens avec d’autres problèmes combinatoires, en particulier pour des matrices modélisant les données réelles d’ADN. Nous proposons des al- gorithmes adaptés, améliorant expérimentalement la robustesse sur données synthétiques et réelles, bien que moins clairement que la deuxième contribution. La quatrième contribution présente le problème de sériation avec duplication, motivé par l’assemblage de génomes cancéreux via des données de conformation spa- tiale, que nous tentons de résoudre avec un algorithme de projections alternées fondé en partie sur les méthodes de sériation robuste, sur données synthétiques.

Large-scale optimisation problems are usually hard to solve optimally. Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred. This thesis focuses on multi-objective local search (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself.While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms.We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.; Les problèmes d’optimisation à grande échelle sont généralement difficiles à résoudre de façon optimale. Des algorithmes d’approximation tels que les métaheuristiques, capables de trouver rapidement des solutions sous-optimales, sont souvent préférés. Cette thèse porte sur les algorithmes de recherche locale multi-objectif (MOLS), des métaheuristiques capables de traiter l’optimisation simultanée de plusieurs critères. Comme de nombreux algorithmes, les MOLS exposent de nombreux paramètres qui ont un impact important sur leurs performances. Ces paramètres peuvent être soit prédits et définis avant l’exécution de l’algorithme, soit ensuite modifiés dynamiquement.Alors que de nombreux progrès ont récemment été réalisés pour la conception automatique d’algorithmes, la grande majorité d’entre eux ne traitent que d’algorithmes mono-objectif et l’optimisation d’un unique indicateur de performance. Dans cette thèse, nous étudions les relations entre la conception automatique d’algorithmes et l’optimisation multi-objective.Nous passons d’abord en revue les stratégies MOLS possibles et présentons un framework MOLS général et hautement configurable. Nous proposons également MO-ParamILS, un configurateur automatique spécialement conçu pour gérer plusieurs indicateurs de performance. Nous menons ensuite plusieurs études sur la conception automatique de MOLS sur de multiples problèmes combinatoires bi-objectifs. Enfin, nous discutons deux extensions de la configuration d’algorithme classique : d’abord l’intégration des mécanismes de contrôle de paramètres, pour bénéficier de multiples prédictions de configuration; puis l’utilisation séquentielle de plusieurs configurations.

Les modèles graphiques probabilistes unifient la théorie des probabilités et les modèles graphiques via des variables aléatoires reliées entre elles par une distribution de loi jointe décomposable. L’objectif étudié ici est connu sous le nom de Maximum A Posteriori dans les champs aléatoires de Markov et de Most Probable Explanation dans les réseaux bayésiens, consiste à trouver une affectation globale de toutes les variables ayant une probabilité maximale ou de manière équivalente une énergie minimale. Les méthodes de résolution MAP/MPE sont qualifiées habituellement de complète ou incomplète, selon leur capacité à prouver l’optimalité ou non. Alors que la plupart des méthodes complètes reposent sur la recherche arborescente, les méthodes incomplètes reposent, quant à elles, sur la recherche locale. Dans cet article, nous proposons une approche itérative potentiellement complète au-dessus d’une recherche à voisinages variables qui utilise la recherche arborescente partielle dans son exploration locale des voisinages. La méthode hybride qui en résulte a été evaluée sur un large éventail de benchmarks issus de l’analyse d’images, la reconnaissance de formes, l’allocation de ressources, la bio-informatique, la bio-physique. . . Les résultats montrent que comparée aux méthodes de recherche arborescente existantes, notre méthode offre un meilleur compromis entre le comportement anytime et la preuve d’optimalité. Enfin, l’expérimentation de notre version parallèle sur des instances difficiles issues de la conception de protéines a mis en évidence l’efficacité de la version parallèle pour trouver des bonnes solutions. Le solveur est librement téléchargeable sur https:/ / github.com/ toulbar2/ toulbar2., Graphical models factorize a global probability distribution/energy function as the product/sum of local functions. A major inference task, known as MAP in Markov Random Fields and MPE in Bayesian Networks, is to find a global assignment of all the variables with maximum probability/minimum energy. A usual distinction on MAP/MPE solving methods is complete/incomplete, i.e. the ability to prove optimality or not. Most complete methods rely on tree search, while incomplete methods rely on local search. Among them, we study Variable Neighborhood Search (VNS) for graphical models. In this paper, we propose an iterative approach above VNS which uses (partial) tree search inside its local neighborhood exploration. The resulting hybrid method offers a better compromise between completeness and anytime behavior than existing tree search methods while still being competitive for proving optimality. We further propose a parallel version of our method improving its anytime behavior on difficult instances coming from a large graphical model benchmark. Last we experiment on the challenging minimum energy problem found in Computational Protein Design, showing the practical benefit of our parallel version. Solver is available at https:/ / github.com/ toulbar2/ toulbar2.

Embedded systems dedicated to aeronautics or automotive interact permanently with their environment. They get information from their sensors, process the data and react with their actuators. Such systems have to execute the functionalities correctly, but also to process them within the allocated time. This feature classifies those systems in the category of real-time systems. In the cited domains, those functionalities are originally defined accordingly to the dynamics of the system and their number can reach several thousand. The real-time operating systems, software which handles the processing of those functionalities on the hardware, generally limit the number of functionalities, due to the overhead caused by their management. In this work, we are interested in techniques that reduce the number of those functionalities so to overstep those restrictions. We propose clustering algorithms that ensure that timing constraints are respected. These methods are applied to monoprocessor and multiprocessor architecture with communicating processes.; Les systèmes embarqués des domaines de l'aéronautique ou de l'automobile sont en interaction permanente avec leur environnement. Ils récupèrent de l'information depuis leurs capteurs, traitent les données et réagissent par le biais de leurs actionneurs. Ces systèmes critiques se doivent non seulement de produire des résultats corrects du point de vue logique mais aussi de les réaliser dans le temps imparti. Cette particularité les classe dans la famille des systèmes temps réel. Dans les domaines cités, les fonctionnalités sont à l'origine définies au regard de la dynamique du système et leur nombre peut atteindre plusieurs milliers. Les systèmes d'exploitation temps réel, logiciels responsables du traitement de ces fonctionnalités sur le matériel, limitent généralement le nombre de traitements implantables, en raison des surcoûts engendrés par leur gestion. Dans ce travail, nous nous intéressons donc à des techniques de réduction du nombre de ces traitements, de manière à passer outre les limitations des systèmes d'exploitation temps réel. Nous proposons des algorithmes de regroupement qui assurent que les contraintes de temps soient respectées. Ces méthodes visent des architectures monoprocesseurs et multiprocesseurs pour des traitements communicants.

National audience

Lorsque l’on cherche à résoudre des problèmes d’optimisation combinatoire difficiles, trouver une solution optimale par les méthodes complètes peut s’avérer impraticable. Dans un tel contexte, on peut déterminer des solutions approchées grâce à l’utilisation d’heuristiques. Parmi elles, les métaheuristiques sont une forme générique d’algorithmes approchés facilement applicables à une large gamme de problèmes.Nos travaux de recherche sur les métaheuristiques cherchent à s’abstraire au maximum des spécificités des problèmes d’optimisation en les modélisant notamment sous forme de paysages de recherche à explorer. Cette abstraction, proposée en 1932 en biologie pour modéliser la relation entre génotype des individus et chances de reproduction, a été reprise plus récemment en optimisation combinatoire afin de mettre en relation la qualité des solutions avec les valeurs prises par les variables de décision. Dans ce contexte, nous avons étudié principalement la résolution de problèmes d’optimisation par les algorithmes de recherche locale.En optimisation mono-objectif, l’étude des climbers classiques de la littérature combinée avec l’analyse de la structure des paysages de recherche nous a permis d’obtenir des résultats parfois à contre-courant de ce qui est fait usuellement dans la communauté. Grâce à ces observations, nous nous sommes proposé d’étudier des stratégies originales pour ces algorithmes de recherche. Les résultats obtenus permettent d’entrevoir des perspectives de recherche importantes dans ce domaine.En optimisation multiobjectif, nous avons proposé des algorithmes de type recherche locale basés sur la notion d’indicateur de qualité. Ces algorithmes, en plus d’être génériques, se sont montrés efficaces sur divers types de problèmes tout en étant peu sensibles au paramétrage. L’utilisation d’indicateurs de qualité permet de surcroît de reformuler les problèmes d’optimisation multiobjectif sous forme de problèmes d’optimisation mono-objectif sur des ensembles et ainsi ouvrir diverses perspectives de recherche.

National audience; Résumé. La gestion de crise pose plusieurs défis aux concepteurs de systèmes d'aide à la décision. Nous proposons dans cet article de traiter la question de la conception de systèmes aptes à orienter intelligemment la coordination des équipes de secours. Un des défis est de permettre au système de fonctionner avec des moyens de communication dégradés. Nous avons développé un modèle d'optimisation par colonies de fourmis, capable de gérer la complexité inhérente dans le déploiement des ressources humaines et matérielles, en tenant compte de l'incertitude des événements présents et futurs d'une crise, ainsi que des effets d'une décision sur le déroulement de la crise, à travers un processus réflexif.

International audience; Graphical models on discrete variables allows to model NP-hard optimization problems where the objective function is factorized into a set of local functions. In the graphical interpretation, each function's scope is represented by a clique. Deterministic graphical models such as Cost Function Network (CFN) aim at minimizing the sum of all functions (or constraints if zero/infinite costs are used). Probabilistic graphical models such as Markov Random Field (MRF) aim at maximizing the product of all functions (or constraints if using zero/one probabilities). A direct (-log) transformation exists between the two frameworks that can also be modeled as weighted MaxSAT or ILP. Strong connections exist between LP itself and bounds used in graphical models. We report a large comparison of state-of-the-art CP/AI/OR exact solvers on several deterministic and probabilistic graphical models coming from the Probabilistic Inference Challenge 2011, the Weighted Partial Max-SAT Evaluation 2013, the MiniZinc Challenge 2012 and 2013, and a library of Cost Function Networks. These competitions are usually restricted to a family of dedicated solvers. We instead compare the efficiency of eight state-of-the-art exact solvers of each optimization language on these encodings. It includes MRF solvers daoopt (https://github.com/lotten/daoopt version 1.1.2), mplp2 (http://cs.nyu.edu/~dsontag/ version 2), toulbar2 (http://mulcyber.toulouse.inra.fr/projects/toulbar2/ version 0.9.6), MaxSAT solver maxhs (http://www.cs.toronto.edu/~jdavies/), ILP solver cplex (version 12.2), and CP solvers numberjack-mistral (http://numberjack.ucc.ie/ version 1.3.40), gecode (http://www.gecode.org/ version 4.2.0), opturion-cpx (http://www.opturion.com version 1.0.2). All the 1062 instances are made publicly available in five different formats (uai, wcsp, wcnf, lp, mzn) and seven formulations at http://genoweb.toulouse.inra.fr/~degivry/evalgm. The results suggest the opportunity for a simple portfolio approach and we give preliminary results based on the numberjack platform.

International audience; Au sein des algorithmes de recherche locale, les méthodes de descente font rarement l'objet d'études expérimentales dédiées. Cependant, ces techniques de recherche sont à la base d'un grand nombre de métaheuristiques modernes et peuvent avoir une influence non négligeable quant à la capacité d'un algorithme à atteindre de bonnes solutions de l'espace de recherche. L'an passé, nous avons comparé des descentes basées sur différentes règles pivot (premier ou meilleur améliorant) et différentes politiques de gestion de la neutralité (descente stricte, stochastique, ou stricte avec perturbations neutres), puis comparé empiriquement leur efficacité sur des paysages de recherche de type NK-landscapes, de différentes tailles et enregistrant différents niveaux de rugosité et de neutralité. Nous étendons cette année cette étude à des paysages de recherche issus de problèmes combinatoires académiques (MAXSAT, QAP, Flow-shop), après avoir introduit des indicateurs de caractérisation des paysages de recherche. Dans une large étude expérimentale, nous montrons que la stratégie du meilleur améliorant est plus efficace sur les paysages lisses et/ou de petites tailles mais est rapidement dominée par la stratégie du premier améliorant sur les paysages plus rugueux et/ou plus grands. Parallèlement, nous indiquons que la descente stochastique, qui accepte indifféremment des voisins neutres tout au long de la recherche (même avant d'avoir atteint un optimum local), permet non seulement une convergence plus rapide de la recherche, mais surtout d'atteindre la plupart du temps des optimums locaux de meilleure qualité. Enfin, une étude sur les NKr-landscapes montre que la création artificielle de plateaux (en arrondissant les valeurs fitness), permet d'atteindre de bien meilleures solutions qu'à partir du paysage originel. En effet, lisser la fonction d'évaluation permet d'éviter d'être piégé trop tôt dans des optimums locaux.

in Springer series Lecture Notes in Computer Science, vol. 8070; International audience; We study the Lazy Bureaucrat scheduling problem (Arkin, Bender, Mitchell and Skiena [1]) in the case of common arrivals and deadlines. In this case the goal is to select a subset of given jobs in such a way that the total processing time is minimized and no other job can fit into the schedule. Our contribution comprises a linear time 4/3-approximation algorithm and an FPTAS, which respectively improve on a linear time 2-approximation algorithm and a PTAS given for the more general case of common deadlines [2,3]. We then consider a selfish perspective, in which jobs are submitted by players who may falsely report larger processing times, and show a tight upper bound of 2 on the approximation ratio of strategyproof mechanisms, even randomized ones. We conclude by introducing a maximization version of the problem and a dedicated greedy algorithm.

This thesis describes my PHD work carried out within the computer science and operations research group of the CREAM3 laboratory, in collaboration with the LISA 4 laboratory, and the support of Angers's General Council. The reported work belongs at the same time to the multi-agent system (MAS), parallelism and metaheuristics domains, and more precisely to develop an intelligent distributed computing system and to compare different information exchange strategies in a distributed memory architecture for parallel computing (Networked PCs). This thesis combines different notions of parallelism, multi-agent paradigm and metaheuristics to provide a high performance method to solve real combinatorial problems. It proves that including information exchange and parallelisation strategies to a population-based algorithm can improve it ability. Instead of using expensive parallel computing facilities, in this work we propose to implement parallel computation model on easily available networked PCs, and present a multi-agent framework to support parallelism. In this model, agents can easily be programmed to initiate the execution of actions autonomously, and they can dynamically move from machine to machine to discover services and communicate with other agents. To evaluate the proposed approach, different kinds of experiments have been conducted to assess the developed system mainly on a vehicule routing problem and an industrial scheduling problem. Results obtained show the efficiency of our approach.; Ce manuscrit décrit les travaux de recherche effectués au cours de ma thèse, au sein de l'équipe informatique et recherche opérationnelle du laboratoire CREAM1, en collaboration avec le laboratoire LISA 2, et avec le soutien du Conseil Général de la ville d'Angers. Ces travaux de recherche se situent à l'intersection des domaines de l'optimisation combinatoire et des systèmes multi-agents. Ils s'inscrivent dans la continuité des propositions de modèles ou de plates-formes pour les métaheuristiques parallèles. Ce rapport réunit différentes notions du parallélisme, du paradigme multi-agents et des métaheuristiques afin d'apporter des méthodes de résolution performantes (robustes et autoadaptatives) à des problèmes d'optimisation combinatoire réels. Il démontre que l'introduction de stratégies de parallélisation et d'échange d'informations à un algorithme à population permet à ce dernier d'améliorer considérablement ses facultés de recherche de solutions. En outre, l'utilisation des agents mobiles permet une exploitation optimale des ressources de calcul inutilisées dans un organisme (laboratoire, entreprise) et de favoriser ainsi l'autonomie des processus de calcul pour pouvoir gérer les éventuelles pannes dans un réseau. Le succès de cette approche dans la résolution d'un problème de tournées de véhicules et d'un problème d'ordonnancement de production, montre l'intérêt pratique de ces méthodes et leurs retombées économiques potentielles. Ce travail de recherche représente l'une des premières explorations des possibilités offertes par deux domaines fort prometteurs de l'intelligence artificielle distribuée et de la recherche opérationnelle. L'union de méthodes auto-adaptatives et d'une puissance de calcul imposante pourrait fort bien se révéler un outil performant pour la résolution de problèmes d'une telle envergure.

Many real-world optimization problems, especially in the field of logistics, have to face a lot of difficulties. Indeed, they are often characterized by large and complex search spaces, multiple conflicting objective functions, and a host of uncertainties that have to be taken into account. Metaheuristics are natural candidates to solve those problems and make them preferable to classical optimization methods. However, the development of efficient metaheuristics results in a complex engineering process. The core subject of this work lies in the design, implementation and experimental analysis of metaheuristics for multiobjective optimization, together with their applications to logistic problems from routing and scheduling. Firstly, a unified view of such approaches is presented and then integrated into a software framework for their implementation, ParadisEO-MOEO. Next, some cooperative approaches combining metaheuristics for multiobjective optimization are proposed. At last, the issue of uncertainty handling is discussed in the context of multiobjective optimization.; De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.

In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs., Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes

The solution to the inexact graph matching problem is the key for defining any type of graph distance. It is even more complex than the exact graph isomorphism problem. On the one hand, inexact graph matching is a combinatorial optimization problem in NP taking into account perturbations inherent in noisy real world environments. Exact graph matching, on the other hand, is a decision problem for which it has not yet been shown if its complexity class is P and which applies only to exactly identical graphs. In this thesis, we study an approach based on genetic algorithms addressing both exact and inexact isomorphisms. We introduce several new crossover operators, some more general for use with any kind of permutation encoding, some specialized which include a greedy heuristic specific to graph matching. We conduct an exhaustive study in order to compare these operators with the existing ones, underlining their respective characteristics, advantages and disadvantages. Furthermore, we examine several aspects for enhancing the algorithm, both theoretical and practical ones, leading to faster execution, better precision or even the assurance of finding the global optimum. We combine the genetic algorithm with generalized black-box heuristics, such as local search, specialized heuristics such as the A* algorithm or practical tools like parallelization techniques. Our final aim is to present a method addressing all different types of graph matching problems, i.e. exact and inexact, isomorphisms of graphs having the same size and sub-graph isomorphisms. We illustrate the generality of our approach with three applications with very distinct properties which cover the different problem types., L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.

There are two relevant stages in Wireless Local Area Network (WLAN) planning. First, a location for each transmitter must be selected and the parameters for all sites must be set. The second important stage is to allocate a frequency to the transmitters in order to provide users with a wireless access in their local network. The objective is to respect financial requirements and to guarantee a given Quality of Service (QoS). The modeling is based on the calculation of the real throughput offered to each service point by the network. It is demonstrated that this real throughput criterion allows a complete modeling of QoS. It unifies the usual criteria of coverage, interferences management and capacity.The optimization addresses the access point location and the frequency assignment problems together. A new algorithm called Random Variable Neighbourhood is defined: at each iteration of this local search, the neighbourhood structure is randomly selected. This algorithm is highly modular and easily combines the location and assignment problems.Collaborations and industrial partnerships were established: WLAN global planning software with Orange Labs and sequential planning solutions with the start-up Trinaps. Finally the modeling problem is further examined by clarifying the links between the real throughput calculations and the SINR. Initially, it is shown that the SINR threshold constraints induce a graph T-coloring problem (necessary condition). To obtain an equivalence accounting for the multiple interferences, a generalization of T-coloring problems for the hypergraphs is introduced. Secondly, an algorithm deducing the SINR thresholds from the real throughput constraints is defined. This new modeling is the base of future developments., Le problème de planification de réseaux WLAN consiste d'une part à positionner et à paramétrer des antennes dans un bâtiment et d'autre part à leur affecter une fréquence afin d'offrir aux clients un accès sans fil au réseau local. Le réseau ainsi construit doit répondre à des critères de couverture et de qualité de service, tout en minimisant le coût financier.Notre modélisation est basée sur le calcul du débit réel offert en chaque point de demande de service du réseau. Nous montrons que ce critère de débit réel permet une modélisation complète de la qualité de service car il unifie les critères habituels de couverture, de gestion des interférences et de capacité.Notre optimisation traite simultanément le problème de placement des points d'accès et le problème d'affectation de fréquences par un algorithme à Voisinages Variables Aléatoires VVA : à chaque itération de cette recherche locale le type de voisinage est tiré au hasard. Cet algorithme est très modulaire et permet facilement de combiner les deux sous problèmes (placement et affection).Ces travaux ont donné lieu à des collaborations et partenariats industriels : logiciel de planification globale des WLAN avec Orange Labs et solutions de planification séquentielle avec la start-up Trinaps.Enfin nous approfondissons la modélisation du problème en explicitant les liens entre le calcul du débit réel et les SINR. Dans une première étape, nous montrons que les contraintes de seuil sur les SINR induisent un problème de T-coloration de graphe (condition nécessaire). Pour obtenir une équivalence rendant compte des interférences multiples, une généralisation du problème de T-coloration pour les hypergraphes est introduite. Dans une seconde étape, nous définissons un algorithme déduisant les seuils de SINR à partir des contraintes sur les débits réels. Cette nouvelle modélisation est la base de nos développements futurs.

DNAmicroarray technologies permit tomeasure simultaneously gene expressions for thousands of genes in a sample and enable to consider molecular cancer diagnosis based on gene expression. Data that are currently available in this field concern a very large number of variables (thousands of gene expressions) relative to a small number of observations (typically under one hundred samples). This thesis deals with the problem of gene selection, which aims to propose a subset of relevant genes in order to build efficient classifiers to recognize different types of tumor. The problem of gene selection is a very hard problem, for which metaheuristics algorithms based on neighbourhood (local search methods) and population (genetic algorithms and memetic algorithms) seem appropriate. In this thesis, we propose several embedded gene selection methods, that combine metaheuristics algorithms with a support vector machine. In these algorithms, the quality of a selected gene subset is evaluated by a linear SVM classifier trained on this subset. Moreover, these algorithms use the relevance measure, given by the linear SVM about each gene, to inform the search process or to build very specialized genetic operators. Experimentations performed on available data sets show very competitive results when compared to the state-ofthe-art works.; Les biopuces permettent de mesurer simultanément l'activité d'un grand nombre de gènes au sein d'échantillons biologiques et de réaliser un diagnostic (reconnaissance tissu sain/tissu cancéreux ou distinction entre différents types de cancer) à partir de ces données. Pour cette tâche de classification, on dispose d'un faible nombre d'échantillons alors que chaque échantillon est décrit par un très grand nombre de gènes. Dans cette thèse, nous nous intéressons à la sélection de gènes qui permet de proposer un sous-ensemble de gènes pertinents afin de construire un classifieur prédisant le type de tumeur qui caractérise un échantillon cellulaire. Le problème de la sélection de gènes est un problème très difficile et les algorithmes métaheuristiques à base de voisinage (méthodes de recherche locale) et à base de populations (algorithmes génétiques et algorithmes mémétiques) semblent bien appropriés pour traiter ce problème. Dans cette thèse, nous proposons plusieurs méthodes de sélection dites intégrées, combinant des algorithmes métaheuristiques avec un séparateur à vaste marge linéaire (SVM). Dans ces algorithmes, la qualité d'un sous-ensemble de gènes sélectionnés est évaluée grâce au classifieur SVM. De plus, nos algorithmes exploitent l'information de pertinence fournie par le classifieur SVM sur les différents gènes pour guider les mécanismes de recherche locale ou pour proposer des opérateurs génétiques spécialisés. Des expérimentations ont été réalisées sur les différents jeux de données disponibles dans la littérature et nos méthodes se révèlent très compétitives par rapport aux travaux existants.

National audience; Le chapitre propose une introduction au domaine de l'optimisation combinatoire multicritère. L'accent est mis sur la complexité de problèmes classiques ainsi que sur des techniques et approches pour l'approximation polynomiale.

International audience; The weighted CSP framework is a soft constraint framework with a wide range of applications. Most current state-of-the-art complete solvers can be described as a basic depth-first branch and bound search that maintain some form of arc consistency during the search. In this paper we introduce a new stronger form of arc consistency, that we call existential directional arc consistency and we provide an algorithm to enforce it. The efficiency of the algorithm is empirically demonstrated in a variety of domains.

National audience; Grâce à elle, le programme informatique résolvant un problème peut s'écrire de manière très simple, presque comme on l'énoncerait dans le langage naturel. Il s'agit simplement d'écrire, les unes après les autres, les différentes contraintes que l'on souhaite voir respectées... et l'ordinateur se débrouille tout seul !