Search

Mathematical programming provides a framework to study and resolve optimization problems, constrained or not. It represents an active domain of Applied Mathematics, for the second half of the 20th century.The aim of this thesis is to solve an non convex, non linear, pure integer, mathematical program, under a linear constraint of equality. This problem, although studied in this dissertation only in the deterministic case, stems from a financial application, known as the large block sale problem, or optimal portfolio liquidation. It consists in selling a (very large) known quantity M of a financial asset in finite time, discretized in N points in time, while maximizing the proceeds of the sale. At each point in time, the sell price is modeled by a penalty function, which reflects the antagonistic behavior of the market in response to our progressive selling flow.From the standpoint of the mathematical programming, this class of problems is NP-hard to solve according to Garey and Johnson, because the non convexity of the objective function imposes on us to adapt classical resolutions methods (Branch and Bound, cuts) for integer variables. In addition, as no general resolution method for this class of problems is known, the methods used for solving must be adapted to the problem specifics.The first part of the thesis is devoted to solve the problem, either exactly or approximately, using Dynamic Programming. We indeed prove that Bellman's equation applies to the problem studied and thus enables to solve it exactly and quickly for small instances. For medium and large instances, for which Dynamic Programming is either not available and/or efficient, we provide lower bounds using different heuristics relying on Dynamic Programming, or local search methods, for which performance (tightness and CPU time) and complexity are studied.The second part of this thesis focuses on the equivalent reformulation of the problem in a factored form, and on its convex relaxation using McCormick's inequalities. We introduce two exact resolution algorithms, which belongs to the Branch and Bound category. They return the global optimum or bound it in limited time.In a third part, dedicated to numerical experiments, we compare our resolution methods between each other and to state of the art solvers. We notice in particular that our bounds are comparable and sometimes even better than solvers' bounds, both free and commercial (e.g LocalSolver, Scip, Baron, Couenne et Bonmin), which we use as benchmark.In addition, we show that our resolution methods may apply to sufficiently regular and increasing penalty functions, especially functions which are currently not handled by some solvers, even though they make economic sense for the problem, as does trigonometric functions or the arctangent function for instance.Numerically, Dynamic Programming does optimally solve the problem, within a minute, for instances of size N1 000 000), our heuristics based on Dynamic Programming, when available, return the best lower bounds. However, we are not able to bound the optimum tightly, since our upper bounds are not thin.; La programmation mathématique fournit un cadre pour l'étude et la résolution des problèmes d'optimisation contraints ou non. Elle constitue une branche active des mathématiques appliquées, depuis la deuxième moitié du XXème siècle.L'objet de cette thèse est la résolution d'un programme mathématique non convexe non linéaire en variables entières, sous contrainte linéaire d'égalité. Le problème proposé, bien qu'abordé dans cette étude uniquement pour le cas déterministe, trouve son origine en finance, sous le nom d'écoulement de larges blocs d'actifs, ou de liquidation optimale de portefeuille. Il consiste à vendre une (très large) quantité M donnée d'un actif financier en temps fini (discrétisé en N instants) en maximisant le produit de cette vente. A chaque instant, le prix de vente est modélisé par une fonction de pénalité qui reflète le comportement antagoniste du marché face à l'écoulement progressif.Du point de vue, de la programmation mathématique, cette classe de problème est NP-difficile résoudre d'après Garey et Johson, car la non-convexité de la fonction objectif impose d'adapter les méthodes classiques de résolutions (Branch and Bound , coupes) en variables entières. De plus, comme on ne connait pas de méthode de résolution générale pour cette classe de problèmes, les méthodes utilisées doivent être adaptées aux spécificités du problème.La première partie de cette thèse est consacrée à la résolution exacte ou approchée utilisant la programmation dynamique. Nous montrons en effet, que l'équation de Bellman s'applique au problème proposé et permet ainsi de résoudre exactement et rapidement les petites instances. Pour les moyennes et grandes instances, où la programmation dynamique n'est plus disponible et/ou performante, nous proposons des bornes inférieures via différentes heuristiques utilisant la programmation dynamique ainsi que des méthodes de recherche locale, dont nous étudions la qualité (optimalité, temps CPU) et la complexité.La seconde partie de la thèse s'intéresse à la reformulation équivalente du problème de thèse sous forme factorisée et à sa relaxation convexe via les inégalités de McCormick. Nous proposons alors deux algorithmes de résolution exacte du type Branch and Bound, qui fournissent l'optimum global ou un encadrement en temps limité.Dans une troisième partie, dédiée aux expérimentations numériques, nous comparons les méthodes de résolutions proposées entre elles et aux solvers de l'état de l'art. Nous observons notamment que les bornes obtenues sont souvent proches et mêmes parfois meilleures que celles des solvers libres ou commerciaux auxquels nous nous comparons (ex : LocalSolver, Scip, Baron, Couenne et Bonmin).De plus, nous montrons que nos méthodes de résolutions peuvent s'appliquer à toute fonction de pénalité suffisamment régulière et croissante, ce qui comprend notamment des fonctions qui ne sont pas actuellement pas prises en charge par certains solvers, bien qu'elles aient un sens économique pour le problème, comme par exemple les fonctions trigonométriques ou la fonction arctangente.Numériquement, la programmation dynamique permet de résoudre à l'optimum, sous la minute, des instances de taille N1 000 000), nos heuristiques à base de programmation dynamique, lorsqu'elles sont disponibles, fournissent les meilleures bornes inférieures, mais nous n'avons pas d'encadrement précis de l'optimum car nos bornes supérieures ne sont pas fines.

Quantum computing is gaining popularity in the computer science community. The awareness of the potential of quantum computing started in 1981, when Richard Feynman first speculated about building a quantum computer. However, until recently, the field has known much skepticism about its long-term practical capabilities to solve problems. In particular, researchers are still facing the challenge of building scalable and reliable quantum computers. Lately, many companies have obtained encouraging results and built quantum machines with enough qubits to start conducting interesting experiments. We chose the worst-case execution-time (WCET) evaluation as the application of our research on quantum computing, as it is crucial for various real-time applications. WCET analysis guarantees that a program's execution time matches all the scheduling and timing constraints. In quantum algorithms history, attention was often given to problems with a particular mathematical structure. The WCETs evaluation, as an opposite, is not a particularly quantum-friendly problem, and it has already proven efficient classical solutions. Hence, it is worth exploring the impact of quantum computing on those kinds of problems, with the spirit of finding new and concrete fields to which quantum computing could bring its potential. If not, research on such specific fields will help to set the boundaries of which applications could benefit from quantum computing. This thesis presents different quantum approaches to perform WCETs evaluations of programs under simplified assumptions.; L'informatique quantique gagne en popularité dans la communauté informatique. La prise de conscience du potentiel de l'informatique quantique a commencée en 1981, lorsque Richard Feynman a imaginé la construction d'un ordinateur quantique. Cependant, le domaine a connu beaucoup de scepticisme quant à ses capacités pratiques à long terme pour résoudre les problèmes. En particulier, les chercheurs tente de relever le défi de construire des ordinateurs quantiques scalables et fiables. Dernièrement, de nombreuses entreprises ont obtenu des résultats encourageants et ont construit des machines quantiques avec suffisamment de qubits pour commencer à mener des expériences intéressantes dessus. Nous avons choisi l'évaluation du pire temps d'exécution (WCET) comme application de nos recherches sur l'informatique quantique, car elle est cruciale pour diverses applications temps réel. L'analyse WCET garantit que le temps d'exécution d'un programme respecte toutes les contraintes d'ordonnancement et de timing. Dans l'histoire des algorithmes quantiques, l'attention a souvent été accordée aux problèmes avec une structure mathématique particulière. L'évaluation des WCET, à l'opposé, n'est pas un problème a priori favorable au contexte quantique, et possède des solutions classiques efficaces déjà éprouvées. Ainsi, il est intéressant d'explorer l'impact de l'informatique quantique sur ce type de problèmes, dans l'esprit de trouver des domaines nouveaux et concrets dans lesquels l'informatique quantique pourrait apporter sa contribution. Si ce n'est pas le cas, la recherche dans ces domaines spécifiques peut aider à définir les limites des applications qui pourraient bénéficier de l'informatique quantique. Cette thèse présente différentes approches quantiques pour effectuer des évaluations WCETs de programmes pour des modèles simplifiés.

This thesis is about models and solution methods for different routing and scheduling problems, which consider legal constraints related to the driving and working time of the truck drivers. These kind of problems require, among other things, coordination between delivery activities, which are defined by a starting date, the service duration at customers (who have time windows), and transport operations, which are defined by starting and finishing dates.In order to solve this models, different optimization methods were proposed to achieve good quality solutions in a reasonable running times. The thesis starts with an introduction, which presents an overview of the problem and the different approaches that have been proposed in the literature to solve it. This literature review follows two lines, problems related with the Truck Driver Scheduling Problem (TDSP) and the combined Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP). The solution methods are developed in order of complexity, starting with models using a restricted number of decision points and ending with models that can handle pre-emption assumptions.The first problem is a Truck Driver Scheduling problem in which breaks and daily rests are only scheduled at the customer locations, which means that transport times between customers must not exceed 4.5 hours. This model is perfectly suited to regional or national transport where distance between two customers does not exceed 4.5h. This problem is the subject of chapter 2: a linear model and a label setting algorithm are proposed and tested on a new set of instances. The second problem addressed concerns to the solution of the Truck Driver Scheduling problem, in which breaks can be scheduled at any point of time, whether at customer locations or in the middle of an activity (driving or service). This problem is more complete because it models more general cases including in particular long distance transports between customers. On this problem different contributions are made: the first is a linear model which extends the model from chapter 2, and three versions of a label setting algorithm. This thesis presents different solutions methods for the TDSP problem while considering all the weekly rules from the European Community Social Legislation, extending in this sense all previous contributions in the literature. In particular, the night working rule that has been whether simplified or discarded in the past. In addition, a new benchmark with detail optimal solutions is provided. The efficiency of the proposed methods and the implications of the different rules in particular the night working constraint are discussed.; Cette thèse porte sur la modélisation et la résolution de différents problèmes d'ordonnancement en intégrant les contraintes légales qui portent sur les temps de conduite et les temps de travail des chauffeurs de camion. Ces problèmes demandent, entre autre, une coordination entre des activités de livraisons, qui se définissent par une date de début et une durée au niveau des clients (qui possèdent des contraintes horaires de passage), et des opérations de transport, qui se définissent par une date de début, une date de fin. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation ont été proposées afin d’obtenir des solutions de bonne qualité dans des temps raisonnables. La thèse commence par une introduction qui présente d’une façon générale le problème et des différentes approches qui ont été proposées dans la littérature pour le résoudre. Cette revue de la littérature suit deux axes, les problèmes liés au Truck Driver Scheduling Problem (TDSP) et le Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP). Les méthodes de résolution sont développées par ordre de complexité, en commençant par des modèles utilisant un nombre restreint de points de décision et en terminant par des modèles qui prennent en compte des hypothèses de preemption. Le premier problème est un problème d'ordonnancement/transport de type Truck and Driver dans lequel les pauses des chauffeurs ne sont planifiés qu'au niveau des clients ce qui impose que les temps de transport de dépassent pas 4h30. Il s'agit d'une modélisation parfaitement adaptée aux transports régionaux ou nationaux dans lesquels les distances entre deux clients ne dépassent pas 4h30. Il faut noter que le retour du camion au dépôt n'est pas modélisé dans l'évaluation de la tournée. Ce problème fait l'objet du chapitre 2 : une modélisation linéaire et un algorithme de programmation dynamique sont proposés et testés sur un nouveau jeu d'instances.Le dernier problème traité concerne la résolution du Truck and Driver, dans lequel les pauses de chauffeurs peuvent être planifié à tout moment, que ce soit chez le client ou au milieu d’une activité (conduit ou service). Ce problème est plus complet car il modélise des cas plus généraux dont en particulier les transports grande distance entre les clients. Sur ce problème différentes contributions sont réalisées : la première concerne la proposition d'un modèle linéaire qui étend le modèle du chapitre 2 et trois versions d’un modèle de programmation dynamique.Cette thèse présente différentes méthodes de solutions pour le problème TDSP tout en considérant les règles hebdomadaires de l’European Community Social Legislation, étendant dans ce sens toutes les contributions précédentes dans la littérature. En particulier, la règle du travail de nuit qui a été simplifiée ou rejetée dans le passé. En outre, un nouveau point de référence avec des solutions optimales détaillées est fourni. L’efficacité des méthodes proposées et les implications des différentes règles, en particulier la contrainte du travail de nuit, sont discutées.

National audience; This paper studies cross-lingual transfer for dependency parsers, with the aim to study ways to mitigate word order differences between the source and the target language in transfer. We show how to learn and implement reordering strategies for target words, that, when used in pre-processing, allow us to improve the parsing accuracy in a zero-shot transfer scenario.; Cet article s’intéresse au transfert cross-lingue d’analyseurs en dépendances et étudie des méthodes pour limiter l’effet potentiellement néfaste pour le transfert de divergences entre l’ordre des mots dans les langues source et cible. Nous montrons comment apprendre et implémenter des stratégies de réordonnancement, qui, utilisées en prétraitement, permettent souvent d’améliorer les performances des analyseurs dans un scénario de transfert « zero-shot ».

International audience; Le Time Dependent Traveling Salesman Problem (TD-TSP) est une généralisation du problème du voyageur de commerce où les temps de trajet varient au cours de la journée, ce qui permet de tenir compte du trafic pour planifier des tournées de livraison en contexte urbain. Le TD-TSP with Time-Windows (TD-TSPTW) généralise ce problème en ajoutant des contraintes sur les heures de passage aux points de livraison. Les approches de résolution existantes passent mal à l'échelle ou sont peu adaptées pour prendre en compte des contraintes supplémentaires telles que des fenêtres temporelles. Par conséquent, nous introduisons dans cet article une approche hybride de résolution du TD-TSPTW, basée sur la programmation dynamique, qui a pour ambition de trouver rapidement de des solutions approchées tout en permettant de réaliser des preuves d'optimalité. Les premiers résultats montrent que cette approche est compétitive dans le cas où les temps de trajet sont variables mais également dans le cas particulier où ils sont constants.

Organisation des capacités hospitalières en réanimation durant une période de crise épidémiologique

We are interested in the parallelization of a class of non-serial polyadic dynamic-programming problems in this thesis. These problems are characterized by a strong dependency between subproblems. To design efficient and portable parallel solutions to solve these problems, the CGM (coarse-grained multicomputer) model is the suitable choice because of its simplicity and its compatibility with most supercomputers.A CGM-based parallel algorithm is a succession of computation and communication rounds. The solutions proposed in the literature give the end-user the possibility of minimizing the number of communication rounds or balancing the load between processors because both objectives are conflicting. Moreover, their main drawback is to foster the latency time of processors, which accounts for most of the global communication time.In this work, we propose an irregular partitioning technique of the dependency graph to tackle these conflicting objectives. It consists in subdividing the dependency graph into subgraphs (or blocks) of variable size. It ensures that the blocks of the first steps (or diagonals) are of large sizes to minimize the number of communication rounds. Thereafter, it decreases these sizes along the diagonals to increase the number of blocks in these diagonals and allow processors to stay active as long as possible. These blocks are fairly distributed among processors to minimize their idle time and balance the load between them. Nevertheless, this strategy induces a high latency time of processors. Indeed, varying the blocks' sizes does not enable them to start evaluating some blocks as soon as the data they need are available. To get over this shortcoming, we propose strategies to evaluate a block as a sequence of computation and communication steps of a set of small-size blocks. The experimental results obtained show a significant performance gain compared to the most efficient solutions proposed in the literature., Nous nous intéressons à la parallélisation d'une classe de problèmes de programmation dynamique de type polyadique non-sérial dans cette thèse. Ces problèmes se caractérisent par une forte dépendance entre les sous-problèmes. Pour concevoir des solutions parallèles efficaces et portables à la classe de problèmes sus-citée, le modèle de calcul CGM (coarse-grained multicomputer) est le choix idéal en raison de sa simplicité et de sa compatibilité avec la plupart des superordinateurs.Un algorithme CGM est une succession de rondes de calcul et de communication. Les solutions proposées dans la littérature donnent à l'utilisateur final le choix de minimiser le nombre de rondes de communication ou d'équilibrer la charge des calculs entre les processeurs car ces objectifs sont contradictoires. De plus, leur défaut majeur est de favoriser le temps de latence des processeurs, qui représente la plus grande partie du temps de communication global.Dans ce travail, nous proposons une technique de partitionnement irrégulier du graphe de dépendances pour apporter une solution à ces objectifs contradictoires. Elle consiste à diviser le graphe de dépendances en sous-graphes (ou blocs) de tailles variables. Elle assure que les blocs des premières étapes (ou diagonales) sont de grandes tailles pour minimiser le nombre de rondes de communication. Ensuite, elle réduit leurs tailles le long des diagonales pour augmenter le nombre de blocs dans ces diagonales et permettre aux processeurs de rester actifs le plus longtemps possible. Ces blocs sont distribués de manière équitable sur les processeurs pour minimiser leur temps d'inactivité et équilibrer leurs charges de calcul. Cependant, cette stratégie induit un temps de latence élevé des processeurs. En effet, la variation de la taille des blocs ne leur permet pas de commencer l'évaluation de certains blocs aussitôt que les données dont ils ont besoin sont disponibles. Pour résoudre ce problème, nous proposons des stratégies consistant à évaluer un bloc comme une succession d'étapes de calcul et de communication d'un ensemble de blocs de petite taille. Les résultats expérimentaux obtenus montrent un gain de performance significatif comparé aux meilleures solutions proposées dans la littérature.

To understand the dynamics of interaction between groups of species, for example, in a hosts/parasites (or hosts/symbionts) system, it is essential to consider the process of coevolution. The cophylogeny reconciliation model formulates the coevolution question as an optimization problem. The set of optimal solutions represents different scenarios of coevolution which need to be analyzed separately. The main result of this thesis is a novel approach that addresses the issue of the often huge number of optimal solutions which makes it difficult to analyze the results. We introduce several biologically motivated equivalence relations, each one splitting the solution space into equivalence classes. We propose polynomial-delay algorithms that enumerate the equivalence classes, and the representative solutions, i.e., the solutions taken from each equivalence class. Experimental results are then presented to illustrate the practical benefits of considering equivalence classes as a means of efficiently exploring the solution space of cophylogeny reconciliation. Based on the algorithmic results, a software called Capybara has been developed as a practical tool for analyzing cophylogeny datasets. More generally, in the area of enumeration algorithms, the problem of efficiently enumerating representative solutions is of theoretical importance. In the second part of this thesis, we provide a general framework for the enumeration of the equivalence classes of solutions for a family of optimization problems. We show that this framework can be applied to various dynamic programming problems, of which the cophylogeny problem is a special case.; Pour comprendre la dynamique d'interactions entre des groupes d'espèces, par exemple, dans un contexte hôtes-parasites, il est primordial d'étudier le processus de coévolution. La réconciliation cophylogénétique est un modèle qui traduit la reconstruction de l'histoire coévolutive en un problème d'optimisation combinatoire. L'ensemble des solutions optimales, qui représentent des scénarios coévolutifs différents, peut avoir une taille considérable, rendant l'analyse des résultats difficile. Le résultat principal de cette thèse porte sur une nouvelle méthode qui permet d'explorer l'espace de solutions de manière efficace. D'abord, je définis des relations d'équivalence et propose des algorithmes d'énumération qui produisent la liste des solutions représentatives, c'est-à-dire des solutions appartenant à chacune des classes d'équivalence. Ensuite, je présente des résultats expérimentaux et montre que l'analyse des classes d'équivalence aide à mieux étudier des jeux de données biologiques. Basé sur nos résultats algorithmiques, un logiciel appelé Capybara a été développé comme un nouvel outil pratique pour l'analyse cophylogénétique. Plus généralement, l'énumération des classes d'équivalence des solutions est un problème théorique important. Dans la seconde partie de la thèse, je présente un cadre général au sein duquel l'énumération efficace des classes d'équivalence est possible. Je propose un algorithme qui énumère les classes d'équivalence des solutions pour une famille de problèmes, en particulier, des problèmes où s'applique la technique de programmation dynamique.

To understand the dynamics of interaction between groups of species, for example, in a hosts/parasites (or hosts/symbionts) system, it is essential to consider the process of coevolution. The cophylogeny reconciliation model formulates the coevolution question as an optimization problem. The set of optimal solutions represents different scenarios of coevolution which need to be analyzed separately. The main result of this thesis is a novel approach that addresses the issue of the often huge number of optimal solutions which makes it difficult to analyze the results. We introduce several biologically motivated equivalence relations, each one splitting the solution space into equivalence classes. We propose polynomial-delay algorithms that enumerate the equivalence classes, and the representative solutions, i.e., the solutions taken from each equivalence class. Experimental results are then presented to illustrate the practical benefits of considering equivalence classes as a means of efficiently exploring the solution space of cophylogeny reconciliation. Based on the algorithmic results, a software called Capybara has been developed as a practical tool for analyzing cophylogeny datasets. More generally, in the area of enumeration algorithms, the problem of efficiently enumerating representative solutions is of theoretical importance. In the second part of this thesis, we provide a general framework for the enumeration of the equivalence classes of solutions for a family of optimization problems. We show that this framework can be applied to various dynamic programming problems, of which the cophylogeny problem is a special case.; Pour comprendre la dynamique d'interactions entre des groupes d'espèces, par exemple, dans un contexte hôtes-parasites, il est primordial d'étudier le processus de coévolution. La réconciliation cophylogénétique est un modèle qui traduit la reconstruction de l'histoire coévolutive en un problème d'optimisation combinatoire. L'ensemble des solutions optimales, qui représentent des scénarios coévolutifs différents, peut avoir une taille considérable, rendant l'analyse des résultats difficile. Le résultat principal de cette thèse porte sur une nouvelle méthode qui permet d'explorer l'espace de solutions de manière efficace. D'abord, je définis des relations d'équivalence et propose des algorithmes d'énumération qui produisent la liste des solutions représentatives, c'est-à-dire des solutions appartenant à chacune des classes d'équivalence. Ensuite, je présente des résultats expérimentaux et montre que l'analyse des classes d'équivalence aide à mieux étudier des jeux de données biologiques. Basé sur nos résultats algorithmiques, un logiciel appelé Capybara a été développé comme un nouvel outil pratique pour l'analyse cophylogénétique. Plus généralement, l'énumération des classes d'équivalence des solutions est un problème théorique important. Dans la seconde partie de la thèse, je présente un cadre général au sein duquel l'énumération efficace des classes d'équivalence est possible. Je propose un algorithme qui énumère les classes d'équivalence des solutions pour une famille de problèmes, en particulier, des problèmes où s'applique la technique de programmation dynamique.

International audience

In this thesis, we are interested in problems that can be formulated in the form of a dynamic program and additional linear constraints. To solve these problems, iterative methods of state space aggregation have been used in the literature. We propose a generic formalism for these methods. We identified a common structure for the different methods, and highlighted their main ingredients. The aim of this formalism is to unify these methods and to show key points so that these methods can be developed more easily for new problems. To allow these methods to be competitive, several problems must be solved: which relaxation choose, which state space, how to refine relaxation at each iteration, which solving method to choose for the relaxations, ... The difficulty of these problems is in the fact that these choices strongly depend on the problem. We propose elements that can be used in a generic way, and others specific to the problems studied. To validate our approach, we applied one of them to the temporal knapsack problem. Successive Sublimation Dynamic Programming method has shown competitive results with the literature, notably thanks to a choice of dimension based on the evolution of the network, a partial enumeration of possible decisions at each state and different tests of dominance and feasibility. In a second step, we compare the performance of our generic implementation with a specialised implementation on these problems. Finally, these methods have been confronted with a less classical industrial problem: a problem of using phytosanitary treatments on vines in which the sub-problems can be formulated as large dynamic programmes.; Dans cette thèse, nous nous intéressons à des problèmes pouvant se formuler sous la forme d’un programme dynamique et de contraintes linéaires additionnelles. Pour résoudre ces problèmes, des méthodes itératives d’agrégation de l’espace d’états ont été utilisées dans la littérature. Nous proposons un formalisme générique pour ces méthodes. Nous avons identifié une structure commune aux différentes méthodes, et mis en avant leurs ingrédients principaux. Le but de ce formalisme est d’unifier ces méthodes et de montrer les points clés pour que ces méthodes puissent être développées plus facilement pour de nouveaux problèmes. Pour permettre à ces méthodes d’être compétitives, plusieurs problématiques doivent être résolues : quelle relaxation choisir, quel espace d’état, comment raffiner la relaxation à chaque itération, quelle méthode de résolution choisir pour les relaxations, ... La difficulté de ces problématiques réside dans le fait que ces choix dépendent fortement du problème. Nous proposons des éléments qui peuvent être utilisés de manière générique, et d’autres spécifiques aux problèmes étudiés. Pour valider notre approche, nous avons appliqué l’une d’elles sur le problème de sac-à- dos temporel. La méthode Successive Sublimation Dynamic Programming a montré des résultats compétitifs avec la littérature, notamment grâce à un choix de dimension basé sur l’évolution du réseau, une énumération partielle des décisions possibles à chaque état et différents tests de dominances et de faisabilités. Nous comparons dans un deuxième temps les performances de notre implémentation générique avec une implémentation spécialisée sur ces problèmes. Enfin, ces méthodes ont été confrontées à un problème industriel moins classique : un problème d’utilisation de traitements phytosanitaires sur des vignes dans lequel les sous-problèmes peuvent être formulés comme des programmes dynamiques de grande taille.

The transportation sector is a major contributor to both air pollution and greenhouse gas emissions. Hybrid electric vehicles can reduce fuel consumption and CO2 emissions by optimizing the energy management of the powertrain. This study examines the trade-off between regulated pollutant emissions and hybrid powertrain efficiency. In the first part of the work, three-dimensional dynamic programming is used with a weighted objective function to determine the optimal distribution of a power request between the thermal engine and the electric motor. In the second part, we modify the control variable in order to take into account the engine actuators (intake pressure, air fuel ratio, and ignition timing). The purpose of this second control problem is to identify the potential differences between conventional solutions and optimal engine control in the context of hybridization. The thermal dynamics of the three-way catalyst are taken into account in order to model the aftertreatment efficiency. Experimental campaigns are conducted on spark-ignition engines to introduce simplified models for emissions, exhaust gas temperature, catalyst heat transfers and efficiency. The convergence of the results is analyzed with respect to the discretization parameters. Parametric studies evaluate the influence of the weighting factor, driving cycle (NEDC, WLTC), electric motor and battery sizing, as well as emission and catalyst modeling parameters. We assess the impact of including the sparkignition engine’s actuators as control variables, focusing on the interdepence between the three parameters (intake pressure, air fuel ratio, and ignition timing). We discuss the difference between the optimal engine control that we calculated for a hybrid vehicle and the standard approach in a conventionnal powertrain., Le secteur des transports est un des principaux contributeurs aux émissions de gaz à effet de serre et à la pollution de l’air. Les véhicules hybrides électriques ont été introduits pour réduire la consommation de ressources fossiles et les émissions de CO2 en optimisant l’efficacité énergétique de la motorisation. Cette thèse s’intéresse au compromis qui peut exister entre cet objectif et la réduction des émissions de polluants réglementés. Dans la première partie du travail, la programmation dynamique à trois dimensions est utilisée avec une fonction objectif qui pondère les deux critères pour déterminer la répartition optimale de puissance entre le moteur thermique et la machine électrique. La seconde partie consiste à introduire les paramètres de contrôle rapproché du moteur thermique (pression d’admission, richesse et avance à l’allumage) dans la méthode d’optimisation. L’objectif est d’identifier les différences potentielles entre la commande optimale du moteur hybridé et les stratégies habituellement utilisées pour les véhicules conventionnels. La dynamique thermique du catalyseur trois voies est modélisée pour évaluer l’efficacité du système de dépollution. Des campagnes de mesures sur deux moteurs à allumage commandé permettent de formuler des modèles simplifiés des émissions de la température des gaz, des coefficients de transferts thermiques et des efficacités du catalyseur. La convergence des résultats est validée au regard des paramètres d’optimisation (finesse de la discrétisation en particulier). Des études paramétriques permettent d’évaluer l’influence sur les résultats du facteur de pondération, du cycle de conduite (NEDC, WLTC), du dimensionnement des composants, et de certains paramètres de modélisation. L’optimisation du contrôle rapproché du moteur est analysée, en particulier concernant l’interdépendance entre les trois variables considérées. La différence entre les stratégies conventionnelles de contrôle du moteur et les résultats obtenus est discutée.

A complex system is a collection of subsystems which are independent enough to be distinguished but linked together in significant ways. This thesis considers the optimization of complex systems within the framework of multiobjective optimization and focuses on a representation of complex systems as coupled systems, meaning that the interaction between subsystems is modeled by coupling constraints, i.e. constraints involving variables from different subsystems.After having recalled the basic notions of multiobjective optimization and of dominance filtering algorithms, we introduce coupled problems, and define the key concept of decomposition in the multiobjective case. A simple implementation of decomposition already yields performance improvement in the resolution of uncoupled problems, but we provide further algorithmic improvements to the combination of solutions from subproblems and the elimination of dominated combinations, using notions of bounding boxes and of unidirectional dominance filtering algorithms.Beyond the uncoupled case, the main challenge of complex systems optimization remains to take coupling constraints into account, while never having to consider whole complex system optimization problem at once. We propose generic restrictions and relaxations of coupling constraints, which yield upper and lower bounds set on the set non-dominated set of a coupled problem. We show that bound sets can be obtained using decomposition.Finally, we present an application problem: a multiobjective multilocation assignment problem. We show that it admits a dynamic programming resolution method, and we show how decomposition can be used to improve on this initial resolution method. On the one hand, the sequential decision process can itself be broken down into independent subsequences. On the other hand, reasoning using bounds or bound sets obtained by decomposition can be used to speed up the sequential decision process by eliminating partial solutions early., Un système complexe peut être vu comme une collection de sous-systèmes irréductiblement liés mais assez indépendants pour être distingués. Cette thèse considère l'optimisation de systèmes complexes dans le cadre multi-objectifs. L'interaction entre sous-systèmes d'un système complexe y prend la forme de contraints couplantes, c’est-à-dire faisant intervenir des variables issues de différents sous-systèmes.Après avoir rappelé les fondements de l'optimisation multi-objectifs et de l’algorithmique de filtrage par dominance, nous présentons la notion de système couplé, et définissons dans le cas multi-objectifs celle, centrale, de décomposition. Une implémentation simple de la décomposition suffit à améliorer le temps de résolution de problèmes non-couplés. Nous proposons de surcroit des méthodes algorithmiques avancées pour la combinaison de solutions de sous-problèmes et l'élimination des combinaison dominées, utilisant les notions de boîte bornante et d’algorithme unidirectionnel de filtrage par dominance.Le défi principal de l'optimisation de systèmes complexes reste de prendre en compte les contraintes couplantes, tout en évitant de considérer l'entièreté du problème original en même temps. Nous proposons des restrictions et relaxations génériques des contraintes couplantes de problèmes couplés, permettant d'obtenir des ensembles bornant supérieurement et inférieurement l'ensemble de solutions non-dominées. Nous montrons que ceux-ci peuvent être calculés en tirant parti de la décomposition.Enfin, nous présentons un problème d’application : une affectation multi-site multi-objectifs sous contraintes de ressources. Nous montrons que ce problème admet un algorithme de résolution par la programmation dynamique, et comment la décomposition peut être utilisée pour améliorer cette méthode initiale. D’une part, le processus séquentiel de décision peut lui-même être décomposé en sous-séquences indépendantes. D’autre part, des bornes ou des ensembles bornant obtenus par décomposition peuvent être utilisés pour accélérer le processus séquentiel de décision par l’élimination précoce de solutions partielles.

This PhD dissertation studies the modeling of prevention effort and its relation to market insurance. The three chapters capture different aspects of this problematic, from the investi- gation of a criteria more in line with actuarial practices to a study of the insurer’s point of view and by examining the effect of risk perception biases and the effect of a continuous-time framework. Chapter 1 models the relationship between an insurer and an insured in the form of a Stack- elberg game. In this game, the insurer plays first by offering an insurance contract in the form of safety loading. The insured then plays by choosing the optimal non-proportional in- surance share and prevention effort. Both the insured and the insurer aim to minimize their respective risk measures, which are both coherent. The respective effects of self-insurance and self-protection actions on risk minimization will be studied. In each case, it will be shown that the optimal choices of the insured exist and the optimal contract for the insurer will be characterized. In addition, we show that if the buyer’s risk measure decreases faster in effort than his expected loss, optimal effort is non-decreasing in the safety loading with a potential discontinuity when optimal coverage switches from full to zero. On the contrary, if the de- crease of the buyer’s risk measure is slower than the expected loss, optimal effort may or may not be non-decreasing in the safety loading. Chapter 2 also studies the relationship between self-insurance and market insurance in the form of an optimization problem for an economic agent. Similarly to Chapter 1, this agent determines the non-proportional insurance share and the prevention effort that will optimally reduce his risk measure. In this chapter, the risk measure considered is a distortion risk and is defined from a non-concave distortion function. This makes it possible to take into account potential individual cognitive biases in the perception of risk. The characterization of the optimal solution for the agent allows to bring a new conclusion in the relation between self-insurance and market insurance. Self-insurance is no longer only substitutable for market insurance, it can also be complementary to the latter, depending on the sensitivity of the prevention effort to the price of the insurance. Chapter 3 focuses on self-protection in the form of a problem of expected utility maximization in time-dynamic version. This takes the form of a stochastic control problem in which the agent chooses his insurance coverage and his prevention effort which is time-dynamic. The problem can be separated into two sub-problems, the first is the optimization in the effort and the second is in the insurance coverage. As the individual wants to obtain the greatest possible final wealth, he seeks to maximize the expectation of the exponential utility of this wealth. The wealth of the agent can be seen as the solution of a backward stochastic differential equation with jumps, we show that this equation admits a unique solution that is also explicit. In particular, we obtain that the optimal prevention effort is constant. The initial distribution of the loss process, when there is no effort, is given by a particular Lévy process: a compound Poisson process. The fact that the optimal effort is constant says that the Lévy property is preserved under exponential utility maximization. The analysis of the insurance coverage optimization gives a sufficient condition to obtain the existence of an optimal level of coverage. The individual can then take out insurance by providing a prevention effort that will allow him to maximize his satisfaction or choose not to take out the contract but nevertheless take part in self-protection actions, Cette thèse de doctorat porte sur la modélisation de l’effort de prévention et de sa relation avec l’assurance de marché. Chacun des chapitres la composant, tente de capturer différents aspects de cette problématique, de l’étude d’un critère conforme aux pratiques actuarielles à celui du côté de l’offre en assurance, en passant par l’inclusion de biais de perception du risque et par une approche de la prévention en temps dynamique. Le chapitre 1 modélise la relation entre un assureur et un assuré sous la forme d’un jeu de Stackelberg. Dans ce jeu, l’assureur joue en premier en proposant un contrat d’assurance sous la forme d’un facteur de chargement. L’assuré joue ensuite en choisissant le taux de couverture et son effort de prévention optimaux. L’assuré comme l’assureur ont pour but de minimiser leurs mesures de risque respectives qui sont toutes deux cohérentes. Les effets respectifs de l’auto-assurance et l’auto-protection, sur la minimisation du risque seront étudiés. Dans chaque cas, il sera montré que les choix optimaux de l’assuré existent et le contrat optimal pour l’assureur sera caractérisé. De plus, il sera montré que si la mesure de risque de l’agent décroit plus rapidement que l’espérance de sa perte, alors l’effort optimal est croissant avec le facteur de chargement avec une discontinuité potentielle lorsque la couverture optimale passe de complète à nulle. Cependant, dans le cas contraire l’effort optimal peut être croissant ou décroissante en fonction du facteur de chargement. Le chapitre 2 étudie la relation entre auto-assurance et assurance de marché également sous la forme d’un problème d’optimisation pour un agent. De manière similaire au chapitre 1, cet agent doit déterminer le taux de couverture et l’effort de prévention qui réduiront de manière optimale sa mesure de risque. La mesure de risque considérée est dite de distorsion et est définie à partir d’une fonction de distorsion non concave. Ceci permet de tenir compte de biais cognitifs individuels potentiels dans la perception du risque. La caractérisation de la solution optimale pour l’agent permet d’apporter une nouvelle conclusion dans la relation entre auto-assurance et assurance de marché. L’auto-assurance n’est plus seulement substituable à l’assurance de marché, elle peut être également complémentaire à celle-ci, suivant la sensibilité de l’effort de prévention au prix de l’assurance. Le chapitre 3 se concentre sur l’auto-protection en proposant un problème de maximisation d’utilité espérée en version dynamique. Ceci se présente sous forme d’un problème de contrôle stochastique dans lequel l’agent choisit sa couverture assurantielle et son effort de prévention qui est dynamique. Le problème peut être séparé en deux sous-problèmes, le premier est une optimisation en l’effort et le second en la couverture assurantielle. Comme l’individu veut obtenir la richesse finale la plus importante possible, il cherche à maximiser l’espérance de l’utilité exponentielle de cette richesse. La richesse de l’agent peut être vue comme la solution d’une équation différentielle stochastique rétrograde à saut, cette équation admet une unique solution et qui est de plus explicite. En particulier, on obtient que l’effort optimal d’auto- protection est constant. La distribution initiale du processus de perte, quand il n’y a pas d’effort, est donnée par un processus de Poisson composé qui est notamment un processus de Lévy. Obtenir un effort optimal constant signifie donc que la propriété de Lévy des processus est préservée par la maximisation d’une espérance d’utilité exponentielle. L’analyse du problème en la couverture assurantielle donne une condition suffisante pour obtenir l’existence d’un niveau de couverture optimal. L’individu pourra alors souscrire à une assurance en fournissant un effort de prévention qui lui permettra de maximiser sa satisfaction ou bien choisir de ne pas souscrire au contrat mais en prenant toutefois part à des actions d’auto-protection

The work in this thesis is separated into two parts. The first part deals with the load planning and sequencing problem for double-stack intermodal railcars, an operational problem found at many rail container terminals. In this problem, containers must be assigned to a platform on which the container will be loaded, and the loading order must be determined. These decisions are made with the objective of minimizing the costs associated with handling the containers, as well as minimizing the cost of containers left behind. The deterministic version of the problem can be cast as a shortest path problem on an ordered graph. This problem is challenging to solve because of the large size of the graph. We propose a two-stage heuristic based on the Iterative Deepening A* algorithm to compute solutions to the load planning and sequencing problem within a five-minute time budget. Next, we also illustrate how a Deep Q-learning algorithm can be used to heuristically solve the same problem.The second part of this thesis considers sequential models in deep learning. A recent strategy to circumvent the exploding and vanishing gradient problem in recurrent neural networks (RNNs) is to enforce recurrent weight matrices to be orthogonal or unitary. While this ensures stable dynamics during training, it comes at the cost of reduced expressivity due to the limited variety of orthogonal transformations. We propose a parameterization of RNNs, based on the Schur decomposition, that mitigates the exploding and vanishing gradient problem, while allowing for non-orthogonal recurrent weight matrices in the model., Le travail de cette thèse est divisé en deux parties. La première partie traite du problème de planification et de séquencement des chargements de conteneurs sur des wagons, un problème opérationnel rencontré dans de nombreux terminaux ferroviaires intermodaux. Dans ce problème, les conteneurs doivent être affectés à une plate-forme sur laquelle un ou deux conteneurs seront chargés et l'ordre de chargement doit être déterminé. Ces décisions sont prises dans le but de minimiser les coûts associés à la manutention des conteneurs, ainsi que de minimiser le coût des conteneurs non chargés. La version déterministe du problème peut être formulé comme un problème de plus court chemin sur un graphe ordonné. Ce problème est difficile à résoudre en raison de la grande taille du graphe. Nous proposons une heuristique en deux étapes basée sur l'algorithme Iterative Deepening A* pour calculer des solutions au problème de planification et de séquencement de la charge dans un budget de cinq minutes. Ensuite, nous illustrons également comment un algorithme d'apprentissage Deep Q peut être utilisé pour résoudre heuristiquement le même problème. La deuxième partie de cette thèse examine les modèles séquentiels en apprentissage profond. Une stratégie récente pour contourner le problème de gradient qui explose et disparaît dans les réseaux de neurones récurrents (RNN) consiste à imposer des matrices de poids récurrentes orthogonales ou unitaires. Bien que cela assure une dynamique stable pendant l'entraînement, cela se fait au prix d'une expressivité réduite en raison de la variété limitée des transformations orthogonales. Nous proposons une paramétrisation des RNN, basée sur la décomposition de Schur, qui atténue les problèmes de gradient, tout en permettant des matrices de poids récurrentes non orthogonales dans le modèle.

In this thesis, we are interested in the resolution by dynamic programming of Multistage Stochastic optimization Problems (MSP).In the first part, we are interested in the approximation of the value functions of a MSP as min-plus or max-plus linear combinations of basic functions. This approach can be interpreted as the tropical algebra analogue of Approximate Dynamic Programming parametric models, notably studied by Bertsekas and Powell.In the simplified framework of multistage deterministic optimisation problems, we introduce an algorithm, called Tropical Dynamic Programming (TDP), which iteratively constructs approximations of value functions as min-plus or max-plus linear combinations. At each iteration, a trajectory of states is randomly drawn and the states forming this trajectory are called trial points. Based on the current approximations of the value functions, TDP then recursively calculates, by going back in time, a new basic function to be added to the current linear min-plus or max-plus combination. The basic function added to the approximation at time t must verify two compatibility conditions: it must be tight at the t-th trial point and valid. In this way TDP avoids discretising the entire state space and tries to emancipate itself from the curse of dimensionality.Our first contribution, within the framework of deterministic multistage optimization problems, is sufficient conditions on the richness of the trial points in order to ensure almost surely the asymptotic convergence of the generated approximations to the value functions, at points of interest.In the second part, the framework of the TDP algorithm was extended to Lipschitz MSPs where the noises are finite and independent. In this framework, max-plus linear and min-plus linear approximations of the value functions are generated simultaneously. At each iteration, in a forward phase, a particular deterministic trajectory of states called the problem-child trajectory is generated. Then, in the backward phase in time, the common approximations are refined by adding basic functions that are tight and valid.Our second contribution is the proof that the difference between the max-plus and min-plus linear combinations thus generated tends towards 0 along the problem-child trajectories. This result generalises a result from Baucke, Downward and Zackeri in 2018 who proved the convergence of a similar scheme, introduced by Philpott, de Matos and Zackeri in 2013, for convex MSPs. However, the algorithmic complexity of the TDP extension presented is highly dependent on the size of the noise support of a given MSP.In the third part, we are interested in quantifying the difference between the values of two MSPs differing only in their scenario tree. Under assumptions of regularities, Pflug and Pichler showed in 2012 that the value of such MSPs is Lipschitz-continuous with respect to the Nested Distance they introduced. However, the computation of the Nested Distance requires an exponential number (w.r.t. the horizon T) of computation of optimal transport problems.Motivated by the success of Sinkhorn's algorithm for computing entropic relaxation of the optimal transport problem, as a third contribution we propose an entropic relaxation of the Nested Distance which we illustrate numerically.Finally, in order to justify the resolution by dynamic programming in more general cases of MSPs, interchange between integration and minimisation must be justified. In the fourth contribution, we establish a general interchange result between integration and minimization which includes some usual results.; Dans cette thèse on s'intéresse à la résolution par programmation dynamique de problèmes d'Optimisation Stochastique Multi-étapes (OSM).En première partie, on s'est intéressé à l'approximation des fonctions valeurs d'un problème OSM par des combinaisons dîtes min-plus ou max-plus linéaires de fonctions basiques. Cette approche s'interprète comme l'analogue en algèbre tropicale de modèles paramétriques en programmation dynamique approximatives, notamment étudiés par Bertsekas et Powell.Dans le cadre simplifié des problèmes d'optimisation multi-étapes déterministes, nous introduisons un algorithme, appelé Programmation Dynamique Tropical (PDT), qui construit itérativement des approximations des fonctions valeurs comme combinaisons min-plus ou max-plus linéaires. A chaque itération, une trajectoire d'états est tirée aléatoirement et les états formant cette trajectoire sont appelés points de raffinements. Compte tenu des approximations courantes des fonctions valeurs, PDT calcule alors récursivement en remontant dans le temps, une nouvelle fonction basique à ajouter à la combinaison min-plus ou max-plus linéaire courante. La fonction basique ajoutée à l'approximation au temps t doit vérifier deux conditions de compatibilité : elle doît être exacte au t-ème point de rafinement et valide. PDT évite ainsi de discrétiser l'espace d'état dans sa totalité et tente de s'émanciper du fléau de la dimension.Notre première contribution, dans le cadre de problèmes multi-étapes déterministes, est l'obtention de conditions suffisantes sur la richesse des points de raffinements afin d'assurer presque sûrement la convergence asymptotique des approximations générées vers les fonctions valeurs, en des points d'intérêts.En seconde partie, on a étendu le cadre de l'algorithme PDT aux problèmes stochastiques multi-étapes Lipschitz où les bruits sont finis et indépendants. Dans ce cadre, on génère simultanément des approximations max-plus linéaires et min-plus linéaires des fonctions valeurs. A chaque itération, lors d'une phase vers l'avant, une trajectoire déterministe d'état particulière appelée trajectoire problème-enfant est générée. Ensuite, lors du phase en arrière dans le temps, les approximations courantes sont raffinées en ajoutant des fonctions basiques qui sont exactes et valides.Notre seconde contribution est la preuve que l'écart entre combinaisons linéaires max-plus et min-plus ainsi générées tend vers 0 le long des trajectoires problèmes-enfants. Ce résultat généralise un résultat de Baucke, Downward et Zackeri de 2018 qui prouvait la convergence d'un schéma similaire, introduit par Philpott, de Matos et Zackeri en 2013, dans le cadre de problèmes OSM convexes. Toutefois, la complexité algorithmique de l'extension de PDT présentée dépend fortement de la taille du support des bruits d'un problème OSM donné. En troisième partie, on s'est intéressé à quantifier l'écart entre les valeurs de deux problèmes OSM ne différant que par leur arbre de scénarios. Sous hypothèses de régularités, Pflug et Pichler ont montré en 2012 que la valeur d'OSM est lipschitzienne par rapport à la Distance Imbriquée qu'ils ont introduite. Toutefois le calcul de la Distance Imbriquée nécessite le calcul d'un nombre exponentiel, en la taille de l'horizon, de problèmes de transport optimal. Motivé par le succès de l'algorithme de Sinkhorn pour calculer une relaxation entropique du problème de transport optimal, en troisième contribution nous proposons une relaxation entropique de la Distance Imbriquée que nous illustrons numériquement. En dernière partie, afin de justifier la résolution par programmation dynamique dans des cas plus généraux, des échanges entre intégration et minimisation doivent être justifiés. En quatrième contribution, nous établissons un résultat général d'échange entre intégration et minimisation qui englobe certains résultats usuels.

In this thesis, we are interested in the resolution by dynamic programming of Multistage Stochastic optimization Problems (MSP).In the first part, we are interested in the approximation of the value functions of a MSP as min-plus or max-plus linear combinations of basic functions. This approach can be interpreted as the tropical algebra analogue of Approximate Dynamic Programming parametric models, notably studied by Bertsekas and Powell.In the simplified framework of multistage deterministic optimisation problems, we introduce an algorithm, called Tropical Dynamic Programming (TDP), which iteratively constructs approximations of value functions as min-plus or max-plus linear combinations. At each iteration, a trajectory of states is randomly drawn and the states forming this trajectory are called trial points. Based on the current approximations of the value functions, TDP then recursively calculates, by going back in time, a new basic function to be added to the current linear min-plus or max-plus combination. The basic function added to the approximation at time t must verify two compatibility conditions: it must be tight at the t-th trial point and valid. In this way TDP avoids discretising the entire state space and tries to emancipate itself from the curse of dimensionality.Our first contribution, within the framework of deterministic multistage optimization problems, is sufficient conditions on the richness of the trial points in order to ensure almost surely the asymptotic convergence of the generated approximations to the value functions, at points of interest.In the second part, the framework of the TDP algorithm was extended to Lipschitz MSPs where the noises are finite and independent. In this framework, max-plus linear and min-plus linear approximations of the value functions are generated simultaneously. At each iteration, in a forward phase, a particular deterministic trajectory of states called the problem-child trajectory is generated. Then, in the backward phase in time, the common approximations are refined by adding basic functions that are tight and valid.Our second contribution is the proof that the difference between the max-plus and min-plus linear combinations thus generated tends towards 0 along the problem-child trajectories. This result generalises a result from Baucke, Downward and Zackeri in 2018 who proved the convergence of a similar scheme, introduced by Philpott, de Matos and Zackeri in 2013, for convex MSPs. However, the algorithmic complexity of the TDP extension presented is highly dependent on the size of the noise support of a given MSP.In the third part, we are interested in quantifying the difference between the values of two MSPs differing only in their scenario tree. Under assumptions of regularities, Pflug and Pichler showed in 2012 that the value of such MSPs is Lipschitz-continuous with respect to the Nested Distance they introduced. However, the computation of the Nested Distance requires an exponential number (w.r.t. the horizon T) of computation of optimal transport problems.Motivated by the success of Sinkhorn's algorithm for computing entropic relaxation of the optimal transport problem, as a third contribution we propose an entropic relaxation of the Nested Distance which we illustrate numerically.Finally, in order to justify the resolution by dynamic programming in more general cases of MSPs, interchange between integration and minimisation must be justified. In the fourth contribution, we establish a general interchange result between integration and minimization which includes some usual results., Dans cette thèse on s'intéresse à la résolution par programmation dynamique de problèmes d'Optimisation Stochastique Multi-étapes (OSM).En première partie, on s'est intéressé à l'approximation des fonctions valeurs d'un problème OSM par des combinaisons dîtes min-plus ou max-plus linéaires de fonctions basiques. Cette approche s'interprète comme l'analogue en algèbre tropicale de modèles paramétriques en programmation dynamique approximatives, notamment étudiés par Bertsekas et Powell.Dans le cadre simplifié des problèmes d'optimisation multi-étapes déterministes, nous introduisons un algorithme, appelé Programmation Dynamique Tropical (PDT), qui construit itérativement des approximations des fonctions valeurs comme combinaisons min-plus ou max-plus linéaires. A chaque itération, une trajectoire d'états est tirée aléatoirement et les états formant cette trajectoire sont appelés points de raffinements. Compte tenu des approximations courantes des fonctions valeurs, PDT calcule alors récursivement en remontant dans le temps, une nouvelle fonction basique à ajouter à la combinaison min-plus ou max-plus linéaire courante. La fonction basique ajoutée à l'approximation au temps t doit vérifier deux conditions de compatibilité : elle doît être exacte au t-ème point de rafinement et valide. PDT évite ainsi de discrétiser l'espace d'état dans sa totalité et tente de s'émanciper du fléau de la dimension.Notre première contribution, dans le cadre de problèmes multi-étapes déterministes, est l'obtention de conditions suffisantes sur la richesse des points de raffinements afin d'assurer presque sûrement la convergence asymptotique des approximations générées vers les fonctions valeurs, en des points d'intérêts.En seconde partie, on a étendu le cadre de l'algorithme PDT aux problèmes stochastiques multi-étapes Lipschitz où les bruits sont finis et indépendants. Dans ce cadre, on génère simultanément des approximations max-plus linéaires et min-plus linéaires des fonctions valeurs. A chaque itération, lors d'une phase vers l'avant, une trajectoire déterministe d'état particulière appelée trajectoire problème-enfant est générée. Ensuite, lors du phase en arrière dans le temps, les approximations courantes sont raffinées en ajoutant des fonctions basiques qui sont exactes et valides.Notre seconde contribution est la preuve que l'écart entre combinaisons linéaires max-plus et min-plus ainsi générées tend vers 0 le long des trajectoires problèmes-enfants. Ce résultat généralise un résultat de Baucke, Downward et Zackeri de 2018 qui prouvait la convergence d'un schéma similaire, introduit par Philpott, de Matos et Zackeri en 2013, dans le cadre de problèmes OSM convexes. Toutefois, la complexité algorithmique de l'extension de PDT présentée dépend fortement de la taille du support des bruits d'un problème OSM donné. En troisième partie, on s'est intéressé à quantifier l'écart entre les valeurs de deux problèmes OSM ne différant que par leur arbre de scénarios. Sous hypothèses de régularités, Pflug et Pichler ont montré en 2012 que la valeur d'OSM est lipschitzienne par rapport à la Distance Imbriquée qu'ils ont introduite. Toutefois le calcul de la Distance Imbriquée nécessite le calcul d'un nombre exponentiel, en la taille de l'horizon, de problèmes de transport optimal. Motivé par le succès de l'algorithme de Sinkhorn pour calculer une relaxation entropique du problème de transport optimal, en troisième contribution nous proposons une relaxation entropique de la Distance Imbriquée que nous illustrons numériquement. En dernière partie, afin de justifier la résolution par programmation dynamique dans des cas plus généraux, des échanges entre intégration et minimisation doivent être justifiés. En quatrième contribution, nous établissons un résultat général d'échange entre intégration et minimisation qui englobe certains résultats usuels.

Je synthétise mes recherches qui portent sur le développement et l'application de modèles et méthodes statistiques pour l'analyse de données omiques. Mes travaux se divisent en quatre axes ou thèmes que voici : (1) la détection de ruptures multiples, (2) l'analyse de données omiques, (3) la classification régularisée et (4) l'évaluation de méthodologies pour l'analyse de données omiques. Les deux premiers thèmes sont plus importants. Pour la détection de ruptures, je présente, de manière unifiée, un certain nombre d'algorithmes récents permettant de retrouver la segmentation maximisant la vraisemblance. Pour l'analyse de données omiques je détaille certaines des difficultés que j'ai rencontrées lors de l'analyse de données omiques. Pour les deux derniers thèmes je résume quelques contributions méthodologiques à la classification régularisée et quelques méthodes de simulation pour l’évaluation de méthodes de segmentation et d'analyse différentielle pour des données omiques.​

The proton exchange membrane fuel cell is a promising electrochemical converter for production of electricity from the decarbonated hydrogen carrier. However, some technological challenges limit its deployment, such as durability, reliability or financial cost. The active fault-tolerant control strategy is one of the solutions to mitigate any system fault according to three actions: diagnosis, decision and control. This study proposes to develop a generic controller module adaptive to health states through neural networks. Dynamic programming controller, reinforcement learning, and echo-state models are combined for the design of the adaptive controller. This controller employs three neural models with specific roles: an actor, a predictor and a critic. Flooding and membrane drying faults are considered in this study. The proposed controller was able to demonstrate interesting capabilities on a simulation fuel cell model in multi-variable regulation for oxygen stoichiometry, membrane pressure difference and temperature. The results show superior performance of the proposed controller compared to a proportional integral derivative controller. Stability analyses were conducted to prove the continuity of the adaptive controller. The controller has been validated experimentally on a single cell test-bench. The configuration of the test-bench imposed constraints specific to an on-line and real-time application. The generic nature of the controller offers the possibility to switch from one configuration to another without having to design another controller. Several tests are carried out for regulation of the zero-pressure difference at the membrane. The controller was validated on the occurrence of flooding and membrane dryness faults, including actuator and water purging disturbances. The approach and the generic controller adaptive to the states of health proposed in this thesis allow to satisfy control requirements regarding the fault-tolerant control strategy. The first interest lies in the compensation of the multilateral effects of faults that lead to unwanted dynamic changes. Another interest is to be able to modify in situ operating conditions, components or even auxiliaries while being able to ensure a stable and optimal control.; La pile à combustible à membrane échangeuse de protons est un convertisseur électrochimique prometteur pour la production électrique à partir du vecteur hydrogène décarboné. Toutefois, certains verrous technologiques limitent encore son déploiement, tels que sa durabilité, sa fiabilité ou son coût financier. La stratégie de contrôle tolérant aux défauts actif est une des solutions pour atténuer tout défaut suivant trois actions : un diagnostic, une décision et un contrôle. Cette étude propose d’élaborer un module contrôleur générique et adaptatif aux états de santé par le biais des réseaux de neurones. Le contrôleur par programmation dynamique, l’apprentissage par renforcement et les modèles à états échoïques sont combinés pour la construction du contrôleur adaptatif. Ce contrôleur emploie trois modèles neuronaux avec des rôles spécifiques : un acteur, un prévisionneur et un critique. Les défauts de noyage et d’assèchement de la membrane sont considérés dans cette étude. Le contrôleur a pu démontrer des capacités intéressantes en simulation pour la régulation multi-variables de la stoechiométrie en oxygène, de la différence de pression à la membrane et de la température. Les résultats montrent des performances supérieures du contrôleur proposé face à un contrôleur proportionnel intégral dérivé. Des analyses de stabilité accompagnent l’étude et prouvent de la continuité du contrôleur adaptatif. Le contrôleur a été validé expérimentalement sur un banc d’essai avec une mono-cellule. La configuration du banc d’essai a imposé des contraintes propres à une application en ligne et en temps réel. Le caractère générique du contrôleur offre ici la possibilité de passer d’une configuration à l’autre sans devoir concevoir un autre contrôleur. Plusieurs tests sont effectués avec comme consigne la différence de pression nulle à la membrane. Le contrôleur a pu être validé sur l’apparition des défauts de noyage, d’assèchement de la membrane, y compris les perturbations en courant, les non-linéarités des actionneurs et de la purge en eau cathodique. La démarche et le contrôleur générique adaptatif aux états de santé proposés dans cette thèse permettent de répondre à des besoins de régulation autour de la stratégie de contrôle tolérant aux défauts. Le premier intérêt réside dans la compensation des effets multilatéraux des défauts qui entraîne des modifications dynamiques non voulues. Un autre intérêt est de pouvoir modifier in situ les conditions opératoires de fonctionnement, les composants ou même les auxiliaires tout en étant capable d’assurer un contrôle stable et optimal.

The proton exchange membrane fuel cell is a promising electrochemical converter for production of electricity from the decarbonated hydrogen carrier. However, some technological challenges limit its deployment, such as durability, reliability or financial cost. The active fault-tolerant control strategy is one of the solutions to mitigate any system fault according to three actions: diagnosis, decision and control. This study proposes to develop a generic controller module adaptive to health states through neural networks. Dynamic programming controller, reinforcement learning, and echo-state models are combined for the design of the adaptive controller. This controller employs three neural models with specific roles: an actor, a predictor and a critic. Flooding and membrane drying faults are considered in this study. The proposed controller was able to demonstrate interesting capabilities on a simulation fuel cell model in multi-variable regulation for oxygen stoichiometry, membrane pressure difference and temperature. The results show superior performance of the proposed controller compared to a proportional integral derivative controller. Stability analyses were conducted to prove the continuity of the adaptive controller. The controller has been validated experimentally on a single cell test-bench. The configuration of the test-bench imposed constraints specific to an on-line and real-time application. The generic nature of the controller offers the possibility to switch from one configuration to another without having to design another controller. Several tests are carried out for regulation of the zero-pressure difference at the membrane. The controller was validated on the occurrence of flooding and membrane dryness faults, including actuator and water purging disturbances. The approach and the generic controller adaptive to the states of health proposed in this thesis allow to satisfy control requirements regarding the fault-tolerant control strategy. The first interest lies in the compensation of the multilateral effects of faults that lead to unwanted dynamic changes. Another interest is to be able to modify in situ operating conditions, components or even auxiliaries while being able to ensure a stable and optimal control.; La pile à combustible à membrane échangeuse de protons est un convertisseur électrochimique prometteur pour la production électrique à partir du vecteur hydrogène décarboné. Toutefois, certains verrous technologiques limitent encore son déploiement, tels que sa durabilité, sa fiabilité ou son coût financier. La stratégie de contrôle tolérant aux défauts actif est une des solutions pour atténuer tout défaut suivant trois actions : un diagnostic, une décision et un contrôle. Cette étude propose d’élaborer un module contrôleur générique et adaptatif aux états de santé par le biais des réseaux de neurones. Le contrôleur par programmation dynamique, l’apprentissage par renforcement et les modèles à états échoïques sont combinés pour la construction du contrôleur adaptatif. Ce contrôleur emploie trois modèles neuronaux avec des rôles spécifiques : un acteur, un prévisionneur et un critique. Les défauts de noyage et d’assèchement de la membrane sont considérés dans cette étude. Le contrôleur a pu démontrer des capacités intéressantes en simulation pour la régulation multi-variables de la stoechiométrie en oxygène, de la différence de pression à la membrane et de la température. Les résultats montrent des performances supérieures du contrôleur proposé face à un contrôleur proportionnel intégral dérivé. Des analyses de stabilité accompagnent l’étude et prouvent de la continuité du contrôleur adaptatif. Le contrôleur a été validé expérimentalement sur un banc d’essai avec une mono-cellule. La configuration du banc d’essai a imposé des contraintes propres à une application en ligne et en temps réel. Le caractère générique du contrôleur offre ici la possibilité de passer d’une configuration à l’autre sans devoir concevoir un autre contrôleur. Plusieurs tests sont effectués avec comme consigne la différence de pression nulle à la membrane. Le contrôleur a pu être validé sur l’apparition des défauts de noyage, d’assèchement de la membrane, y compris les perturbations en courant, les non-linéarités des actionneurs et de la purge en eau cathodique. La démarche et le contrôleur générique adaptatif aux états de santé proposés dans cette thèse permettent de répondre à des besoins de régulation autour de la stratégie de contrôle tolérant aux défauts. Le premier intérêt réside dans la compensation des effets multilatéraux des défauts qui entraîne des modifications dynamiques non voulues. Un autre intérêt est de pouvoir modifier in situ les conditions opératoires de fonctionnement, les composants ou même les auxiliaires tout en étant capable d’assurer un contrôle stable et optimal.

The new generation of wireless systems 5G aims not only to convincingly exceed its predecessor (LTE) data rate but to work with more dimensions. For instance, more user classes were introduced associated with different available operating points on the trade-off of data rate, latency, reliability. New applications, including augmented reality, autonomous driving, industry automation and tele-surgery, push the need for reliable communications to be carried out under extremely stringent latency constraints. How to manage the physical level in order to successfully meet those service guarantees without wasting valuable and expensive resources is a hard question. Moreover, as the permissible communication latencies shrink, allowing retransmission protocol within this limited time interval is questionable. In this thesis, we first pursue to answer those two questions. Concentrating on the physical layer and specifically on a point to point communication system, we aim to answer if there is any resource allocation of power and blocklength that will render an Hybrid Automatic ReQuest (HARQ) protocol with any number of retransmissions beneficial. Unfortunately, the short latency requirements force only a limited number of symbols to possibly be transmitted which in its turn yields the use of the traditional Shannon theory inaccurate. Hence, the more involved expression using finite blocklength theory must be employed rendering the problem substantially more complicate. We manage to solve the problem firstly for the additive white gaussian noise (AWGN) case after appropriate mathematical manipulations and the introduction of an algorithm based on dynamic programming. Later we move on the more general case where the signal is distorted by a Ricean channel fading. We investigate how the scheduling decisions are affected given the two opposite cases of Channel State Information (CSI), one where only the statistical properties of the channel is known, i.e. statistical CSI, and one where the exact value of the channel is provided to the transmitter, i.e., full CSI.Finally we ask the same question one layer above, i.e. the Medium Access Contron (MAC). The resource allocation must be performed now accross multiple users. The setup for each user remains the same, meaning that a specific amount of information must be delivered successfully under strict latency constraints within which retransmissions are allowed. As 5G categorize users to different classes users according to their needs, we model the traffic under the same concept so each user belongs to a different class defining its latency and data needs. We develop a deep reinforcement learning algorithm that manages to train a neural network model that competes conventional approaches using optimization or combinatorial algorithms. In our simulations, the neural network model actually manages to outperform them in both statistical and full CSI case.; La nouvelle génération de systèmes de communication sans fil 5G vise non seulement à dépasser le débit de données du prédécesseur (LTE), mais à améliorer le système sur d'autres dimensions. Dans ce but, davantage de classes d'utilisateurs ont été introduites afin de fournir plus de choix de types de service. Chaque classe est un point différent sur le compromis entre le débit de données, la latence et la fiabilité. Maintenant, beaucoup de nouvelles applications, notamment la réalité augmentée, la conduite autonome, l'automatisation de l'industrie et la téléchirurgie, poussent vers un besoin de communications fiables avec une latence extrêmement faible. Comment gérer la couche physique afin de garantir ces services sans gaspiller des ressources précieuses et coûteuses est une question difficile. En outre, comme les latences de communication autorisées diminuent, l'utilisation d'un protocole de retransmission est contestable. Dans cette thèse, nous tentons de répondre à ces deux questions. En particulier, nous considérons un système de communication point à point, et nous voulons répondre s'il existe une allocation de ressources de puissance et de bande passante qui pourrait rendre le protocole Hybrid Automatic ReQuest (HARQ) avec n'importe quel nombre de retransmissions avantageux. Malheureusement, les exigences de très faible latence obligent à transmettre qu'un nombre limité de symboles. Par conséquent, l'utilisation de la théorie traditionnelle de Shannon est inadaptée et une autre beaucoup plus compliquée doit être employée, qui s'appelle l'analyse à bloc fini. Nous parvenons à résoudre le problème dans le cas du bruit additif blanc gaussien (AWGN) en appliquant des manipulations mathématiques et l'introduction d'un algorithme basé sur la programmation dynamique. À l'étape suivante, nous passons au cas plus général où le signal est déformé par un évanouissement de Rice. Nous étudions comment l'allocation de ressources est affectées étant donné les deux cas opposés d'informations sur l'état du canal (CSI), l'un où seules les propriétés statistiques du canal sont connues (CSI statistique), et l'autre où la valeur exacte du canal est fournie au émetteur(CSI complet).Finalement, nous posons la même question concernant le couche au-dessus, c'est-à-dire le Medium Access Control (MAC). L'allocation des ressources est maintenant effectuée sur plusieurs utilisateurs. La configuration pour chaque utilisateur reste la même, c'est-à-dire qu'une quantité précise de données doit être délivrée sous des contraintes de latence stricte et il y a toujours la possibilité d'utiliser des retransmissions. Comme la 5G classe les utilisateurs en classes d'utilisateurs différentes selon leurs besoins, nous modélisons le trafic d'utilisateurs avec le même concept. Chaque utilisateur appartient à une classe différente qui détermine sa latence et ses besoins en données. Nous développons un algorithme d'apprentissage par renforcement profond qui réussit à entraîner un modèle de réseau de neurones artificiels que nous comparons avec des méthodes conventionnelles en utilisant des algorithmes d'optimisation ou d'approches combinatoires. En fait, dans nos simulations le modèle de réseau de neurones artificiels parvient à les surpasser dans les deux cas de connaissance du canal (CSI statistique et complet).

The new generation of wireless systems 5G aims not only to convincingly exceed its predecessor (LTE) data rate but to work with more dimensions. For instance, more user classes were introduced associated with different available operating points on the trade-off of data rate, latency, reliability. New applications, including augmented reality, autonomous driving, industry automation and tele-surgery, push the need for reliable communications to be carried out under extremely stringent latency constraints. How to manage the physical level in order to successfully meet those service guarantees without wasting valuable and expensive resources is a hard question. Moreover, as the permissible communication latencies shrink, allowing retransmission protocol within this limited time interval is questionable. In this thesis, we first pursue to answer those two questions. Concentrating on the physical layer and specifically on a point to point communication system, we aim to answer if there is any resource allocation of power and blocklength that will render an Hybrid Automatic ReQuest (HARQ) protocol with any number of retransmissions beneficial. Unfortunately, the short latency requirements force only a limited number of symbols to possibly be transmitted which in its turn yields the use of the traditional Shannon theory inaccurate. Hence, the more involved expression using finite blocklength theory must be employed rendering the problem substantially more complicate. We manage to solve the problem firstly for the additive white gaussian noise (AWGN) case after appropriate mathematical manipulations and the introduction of an algorithm based on dynamic programming. Later we move on the more general case where the signal is distorted by a Ricean channel fading. We investigate how the scheduling decisions are affected given the two opposite cases of Channel State Information (CSI), one where only the statistical properties of the channel is known, i.e. statistical CSI, and one where the exact value of the channel is provided to the transmitter, i.e., full CSI.Finally we ask the same question one layer above, i.e. the Medium Access Contron (MAC). The resource allocation must be performed now accross multiple users. The setup for each user remains the same, meaning that a specific amount of information must be delivered successfully under strict latency constraints within which retransmissions are allowed. As 5G categorize users to different classes users according to their needs, we model the traffic under the same concept so each user belongs to a different class defining its latency and data needs. We develop a deep reinforcement learning algorithm that manages to train a neural network model that competes conventional approaches using optimization or combinatorial algorithms. In our simulations, the neural network model actually manages to outperform them in both statistical and full CSI case., La nouvelle génération de systèmes de communication sans fil 5G vise non seulement à dépasser le débit de données du prédécesseur (LTE), mais à améliorer le système sur d'autres dimensions. Dans ce but, davantage de classes d'utilisateurs ont été introduites afin de fournir plus de choix de types de service. Chaque classe est un point différent sur le compromis entre le débit de données, la latence et la fiabilité. Maintenant, beaucoup de nouvelles applications, notamment la réalité augmentée, la conduite autonome, l'automatisation de l'industrie et la téléchirurgie, poussent vers un besoin de communications fiables avec une latence extrêmement faible. Comment gérer la couche physique afin de garantir ces services sans gaspiller des ressources précieuses et coûteuses est une question difficile. En outre, comme les latences de communication autorisées diminuent, l'utilisation d'un protocole de retransmission est contestable. Dans cette thèse, nous tentons de répondre à ces deux questions. En particulier, nous considérons un système de communication point à point, et nous voulons répondre s'il existe une allocation de ressources de puissance et de bande passante qui pourrait rendre le protocole Hybrid Automatic ReQuest (HARQ) avec n'importe quel nombre de retransmissions avantageux. Malheureusement, les exigences de très faible latence obligent à transmettre qu'un nombre limité de symboles. Par conséquent, l'utilisation de la théorie traditionnelle de Shannon est inadaptée et une autre beaucoup plus compliquée doit être employée, qui s'appelle l'analyse à bloc fini. Nous parvenons à résoudre le problème dans le cas du bruit additif blanc gaussien (AWGN) en appliquant des manipulations mathématiques et l'introduction d'un algorithme basé sur la programmation dynamique. À l'étape suivante, nous passons au cas plus général où le signal est déformé par un évanouissement de Rice. Nous étudions comment l'allocation de ressources est affectées étant donné les deux cas opposés d'informations sur l'état du canal (CSI), l'un où seules les propriétés statistiques du canal sont connues (CSI statistique), et l'autre où la valeur exacte du canal est fournie au émetteur(CSI complet).Finalement, nous posons la même question concernant le couche au-dessus, c'est-à-dire le Medium Access Control (MAC). L'allocation des ressources est maintenant effectuée sur plusieurs utilisateurs. La configuration pour chaque utilisateur reste la même, c'est-à-dire qu'une quantité précise de données doit être délivrée sous des contraintes de latence stricte et il y a toujours la possibilité d'utiliser des retransmissions. Comme la 5G classe les utilisateurs en classes d'utilisateurs différentes selon leurs besoins, nous modélisons le trafic d'utilisateurs avec le même concept. Chaque utilisateur appartient à une classe différente qui détermine sa latence et ses besoins en données. Nous développons un algorithme d'apprentissage par renforcement profond qui réussit à entraîner un modèle de réseau de neurones artificiels que nous comparons avec des méthodes conventionnelles en utilisant des algorithmes d'optimisation ou d'approches combinatoires. En fait, dans nos simulations le modèle de réseau de neurones artificiels parvient à les surpasser dans les deux cas de connaissance du canal (CSI statistique et complet).

To meet the vehicle fleet-wide average CO2 targets, the stringent pollutant emissions standards, and the clients’ new demands, the automakers realized the inevitable need to offer more hybrid and electric powertrains. Designing a hybrid powertrain remains however a complex task. It is an intricate system involving numerous variables that are spread over different levels: architecture, component technologies, sizing, and control. The industry lacks frameworks or tools that help in exploring the entire design space and in finding the global optimal solution on all these levels. This thesis proposes a systematic methodology that tries to answer a part of this need. Starting from a set of chosen components, the methodology automatically generates all the possible graphs of architectures using constraint-programming techniques. A tailored representation is developed to picture these graphs. The gearbox elements (clutches, synchronizer units) are represented with a level of details appropriate to generate the new-trend dedicated hybrid gearboxes, without making the problem too complex. The graphs are then transformed into other types of representation: 0ABC Table (describing the mechanical connections between the components), Modes Table (describing the available modes in the architectures) and Modes Table + (describing for each available mode the global efficiency and ratio of the power flow between all the components). Based on these representations, the architectures are filtered and the most promising ones are selected. They are automatically assessed and optimized using a general hybrid model specifically developed to calculate the performance and fuel consumption of all the generated architectures. This model is inserted inside a bi-level optimization process: Genetic Algorithm GA is used on the sizing and components level, while Dynamic Programming DP is used on the control level. A case study is performed and the capability of the methodology is proven. It succeeded in automatically generating all the graphs of possible architectures, and filtering dismissed architectures that were then proven not efficient. It also selected the most promising architectures for optimization. The results show that the proposed methodology succeeded in finding an architecture better than the ones proposed without the methodology (consumption about 5% lower); Pour répondre aux objectifs de consommation des flottes de véhicules, au normes d’émissions de polluants et aux nouvelles demandes de l’usager, les constructeurs automobiles doivent développer des motorisations hybrides et électriques. Réaliser une chaine de traction hybride reste cependant une tâche difficile. Ces systèmes sont complexes et possèdent de nombreuses variables réparties sur différents niveaux : architecture, technologie des composants, dimensionnement et contrôle/commande. L’industrie manque encore d’environnements et d’outils pouvant aider à l’exploration de l’ensemble de l’espace de dimensionnement et à trouver la meilleure solution parmi tous ces niveaux. Cette thèse propose une méthodologie systématique pour répondre au moins partiellement à ce besoin. Partant d’un ensemble de composants, cette méthodologie permet de générer automatiquement tous les graphes d’architectures possibles en utilisant la technique de programmation par contraintes. Une représentation dédiée est développée pour visualiser ces graphes. Les éléments de boites de vitesse (embrayages, synchroniseurs) sont représentés avec un niveau de détails approprié pour générer de nouvelles transmission mécaniques sans trop complexifier le problème. Les graphes obtenus sont ensuite transformés en d’autres types de représentation : 0ABC Table (décrivant les connections mécaniques entre les composants), Modes Table (décrivant les modes de fonctionnement disponibles dans les architectures) et Modes Table + (décrivant pour chaque mode le rendement et le rapport de réduction global des chemins de transfert de l’énergie entre tous les composants). Sur la base de cette représentation, les nombreuses architectures générées sont filtrées et seules les plus prometteuses sont sélectionnées. Elles sont ensuite automatiquement évaluées et optimisées avec un modèle général spécifiquement développé pour calculer les performances et la consommation de toute les architectures générées. Ce modèle est inséré dans un processus d’optimisation à deux niveaux ; un algorithme génétique GA est utilisé pour le dimensionnement des composants et la programmation dynamique est utilisée au niveau contrôle (gestion de l’énergie) du système. Un cas d’étude est ensuite réalisé pour montrer le potentiel de cette méthodologie. Nous générons ainsi automatiquement toutes les architectures qui incluent un ensemble de composants défini à l’avance, et le filtrage automatique élimine les architectures présupposées non efficaces et sélectionnent les plus prometteuses pour l’optimisation. Les résultats montrent que la méthodologie proposée permet d’aboutir à une architecture meilleure (consommation diminuée de 5%) que celles imaginées de prime abord (en dehors de toute méthodologie)

An aircraft engine is made up of several families of materials that undergo multiple degradation mechanisms from their manufacture but also during their flight cycle (take-off, landing, pressurization, pilot manoeuvring,...) or during its rest on the ground. One of these mechanisms is related to the phenomenon of fatigue which represents the degradation of a piece due to repeated cyclic stresses. This degradation results in the initiation of a crack and its propagation until the piece ruptures. The prediction of the propagation lifetime of parts is therefore a very sensitive point since it impacts both the dimensioning (step prior to the design of the pieces) and the maintenance procedures (repair or change of the piece). Propagation lifetime calculations are partly based on the laws of phenomenological evolution describing the rate of progress of the crack in a material as a function of the stress applied. In order to study these data, which are likely to be modelled continuously and which allow several propagation regimes to be observed, we propose a polynomial regression model with several regimes, subject to regularity assumptions (continuity and/or differentiability). Following this, we developed inference methods to estimate the number of regimes, transition times and parameters of each regime. These results will only be usable by the engineering office if they are obtained within reasonable calculation times, i.e. in the order of a few minutes. Each new method has therefore been designed to reduce the computation time required to estimate the model parameters. Moreover, since the number of regimes present in the data is not known a priori, the last two methods we propose do not use any a priori on this number to estimate the model parameters. The work presented in this thesis is the subject of a collaboration between the Probability and Statistics team of the Institut Elie Cartan of the University of Lorraine, the BIGS team of Inria Nancy Grand Est and Safran Aircraft Engines., Un moteur d'avion est constitué de plusieurs familles de matériaux qui subissent de multiples mécanismes de dégradation dès leur fabrication mais également pendant leur cycle de vol (décollage, atterrissage, pressurisation, manœuvre du pilote,...), où encore lors de son repos au sol. Un de ces mécanismes est lié au phénomène de fatigue, qui représente la dégradation subie par une pièce du fait de sollicitations cycliques répétées. Cette dégradation se traduit par l'amorçage d'une fissure et sa propagation jusqu'à rupture de la pièce. La prédiction de la durée de vie en propagation des pièces est donc un point très sensible puisqu'elle impacte à la fois le dimensionnement (étape préalable à la conception des pièces) et les procédures de maintenance (réparation ou changement de la pièce). Les calculs de durées de vie en propagation sont en partie réalisés à partir des lois d'évolutions phénoménologiques décrivant la vitesse d'avancée de la fissure dans un matériau en fonction de la contrainte appliquée. Dans l'objectif d'étudier ces données, qui sont susceptibles d'être modélisées de façon continue et qui laissent observer plusieurs régimes de propagation, nous proposons un modèle de régression polynomiale à plusieurs régimes, soumis à des hypothèses de régularité (continuité et/ou dérivabilité). Suite à cela, nous avons développé des méthodes d'inférence permettant d'estimer le nombre de régimes, les instants de transition et les paramètres de chaque régime. Ces résultats ne seront exploitables par le bureau d'études que s'ils sont obtenus en des temps de calculs raisonnables c'est-à-dire de l'ordre de quelques minutes. Chaque nouvelle méthode a donc été conçue dans l'objectif de réduire les temps de calculs nécessaires à l'estimation des paramètres du modèle. De plus, comme le nombre de régimes présents dans les données n'est pas connu a priori, les deux dernières méthodes que nous proposons n'utilisent aucun a priori sur ce nombre pour estimer les paramètres du modèle. Le travail présenté dans ce mémoire fait l'objet d'une collaboration entre l'équipe de Probabilités et Statistique de l'Institut Elie Cartan de l'université de Lorraine, l’équipe BIGS du centre Inria Nancy Grand Est et la société Safran Aircraft Engines.

The high-value Internet services that have been significantly enhanced with the integration of network virtualization and Software Defined Networking (SDN) technology are increasingly attracting the attention of end-users and major computer network companies (Google, Amazon, Yahoo, Cisco, ...). In order to cope with this high demand, network resource providers (bandwidth, storage space, throughput, etc.) must implement the right models to understand and hold the users' needs while maximizing profits reaped or the number of satisfied requests into the virtual networks. This need is even more urgent that users' requests can be linked, thereby imposing to the InP some constraints concerning the mutual satisfaction of requests, which further complicates the problem. From this perspective, we show that the problem of resource allocation to users based on their requests is a knapsack problem and can therefore be solved efficiently by using the best dynamic programming solutions for the knapsack problem. Our contribution takes the dynamic resources allocation as a multiple knapsack's problem instances on variable value requests., La multitude des services à forte valeur ajoutée offert par Internet et améliorés considérablement avec l'intégration de la virtualisation réseau et de la technologie des réseaux définis par logiciels (Software Defined Networking), suscite de plus en plus l'attention des utilisateurs finaux et des grands acteurs des réseaux informatiques (Google, Amazon, Yahoo, Cisco, ...); ainsi, pour faire face à cette forte demande, les fournisseurs de ressources réseau (bande passante, espace de stockage, débit, ...) doivent mettre en place les bons modèles permettant de bien prendre en main les besoins des utilisateurs tout en maximisant les profits engrangés ou le nombre de requêtes satis-faites dans les réseaux virtuels. Ce besoin est d'autant plus urgent que les requêtes des utilisateurs peuvent être interdépendantes, imposant de ce fait au FIP des contraintes de satisfaction mutuelle des requêtes, ce qui complexifie encore plus le problème. Dans cette optique, nous montrons que le problème d'allocation des ressources aux utilisateurs en fonction de leurs requêtes, se ramène à un problème de sac à dos et peut par conséquent être résolu de façon efficiente en exploitant les meilleures solutions de programmation dynamique pour le problème de sac à dos. Notre contribution considère l'allocation dynamique des ressources comme une application de plusieurs instances du problème de sac à dos sur des requêtes à valeurs variables.

International audience; Dans un contexte de forte pénétration des énergies renouvelables, a fortiori dans un réseau multi-énergies, le stockage thermique est une solution pertinente. Or son fonctionnement utilisant des transferts de chaleur entre plusieurs phases est complexe. Sa modélisation précise ne peut donc que difficilement être prise en compte au sein du problème de gestion optimale d’un réseau multi-énergies. Dans ce travail, nous proposons d’analyser l’impact de la précision du modèle de stockage thermique sur l’efficacité de la gestion d’un réseau de chaleur. Un modèle physique précis et deux modèles linéaires seront comparés sur un cas d’étude, ainsi qu’un métamodèle original : rapide mais capable de prendre en compte la stratification de chaleur ou les pertes thermiques en phase de charge. Ce métamodèle utilise la fonction logistique afin de réduire les dimensions de l’état du stockage. Il est basé sur une matrice d’interpolation construite préalablement à l’aide des nombreuses simulations issues du modèle physique précis. De plus, ce modèle peut être ajusté pour atteindre tous les compromis entre précision et rapidité d’évaluation.

The CGM model is one of the most widely used models for the design of parallel algorithms. It has shown its efficiency in solving several problems modeled by dynamic programming such as the longest common subsequence problem, which is a special case of the one-dimensional sequence alignment problem. This problem consists in aligning two strings of length n to measure their similarity. It is widely used in many fields, particularly in Bioinformatics where n is usually very large. Brubach and Ghurye proposed a sequential solution based on the Four-Russians speed-up that requires O(n^2 / log n) execution time. To the best of our knowledge, there are not yet parallel solutions on the CGM model to solve this problem. This paper is exclusively dedicated to this task. Our solution applies to both local and global similarity computations and is based on Brubach and Ghurye’s sequential algorithm. It requires O(n^2 / p log n) execution time with O(p) communication rounds on p processors., Le modèle CGM est l’un des modèles les plus utilisés pour la conception d’algorithmes parallèles. Il a montré son efficacité pour la résolution de plusieurs problèmes modélisés par la programmation dynamique comme le problème de la plus longue sous-séquence commune, qui est un cas particulier du problème d’alignement de séquence à une dimension. Ce problème consiste à aligner deux chaînes de longueur n afin de mesurer leur similarité. Il est largement utilisé dans de nombreux domaines, en particulier dans la Bio-informatique où n est généralement très grand. Brubach et Ghurye ont proposé une solution séquentielle basée sur l’accélération de Four-Russians qui nécessite un temps d’exécution de O(n^2 / log n). À notre connaissance, il n’existe pas encore de solutions parallèles sur le modèle CGM pour la résolution de ce problème. Ce papier est exclusivement dédié à cette tâche. Notre solution s’applique aux calculs de similarité locaux et globaux, et est basée sur l’algorithme séquentiel de Brubach et Ghurye. Elle nécessite un temps d’exécution de O(n^2 / p log n) avec O(p) rondes de communication sur p processeurs.

To meet the vehicle fleet-wide average CO2 targets, the stringent pollutant emissions standards, and the clients’ new demands, the automakers realized the inevitable need to offer more hybrid and electric powertrains. Designing a hybrid powertrain remains however a complex task. It is an intricate system involving numerous variables that are spread over different levels: architecture, component technologies, sizing, and control. The industry lacks frameworks or tools that help in exploring the entire design space and in finding the global optimal solution on all these levels. This thesis proposes a systematic methodology that tries to answer a part of this need. Starting from a set of chosen components, the methodology automatically generates all the possible graphs of architectures using constraint-programming techniques. A tailored representation is developed to picture these graphs. The gearbox elements (clutches, synchronizer units) are represented with a level of details appropriate to generate the new-trend dedicated hybrid gearboxes, without making the problem too complex. The graphs are then transformed into other types of representation: 0ABC Table (describing the mechanical connections between the components), Modes Table (describing the available modes in the architectures) and Modes Table + (describing for each available mode the global efficiency and ratio of the power flow between all the components). Based on these representations, the architectures are filtered and the most promising ones are selected. They are automatically assessed and optimized using a general hybrid model specifically developed to calculate the performance and fuel consumption of all the generated architectures. This model is inserted inside a bi-level optimization process: Genetic Algorithm GA is used on the sizing and components level, while Dynamic Programming DP is used on the control level. A case study is performed and the capability of the methodology is proven. It succeeded in automatically generating all the graphs of possible architectures, and filtering dismissed architectures that were then proven not efficient. It also selected the most promising architectures for optimization. The results show that the proposed methodology succeeded in finding an architecture better than the ones proposed without the methodology (consumption about 5% lower), Pour répondre aux objectifs de consommation des flottes de véhicules, au normes d’émissions de polluants et aux nouvelles demandes de l’usager, les constructeurs automobiles doivent développer des motorisations hybrides et électriques. Réaliser une chaine de traction hybride reste cependant une tâche difficile. Ces systèmes sont complexes et possèdent de nombreuses variables réparties sur différents niveaux : architecture, technologie des composants, dimensionnement et contrôle/commande. L’industrie manque encore d’environnements et d’outils pouvant aider à l’exploration de l’ensemble de l’espace de dimensionnement et à trouver la meilleure solution parmi tous ces niveaux. Cette thèse propose une méthodologie systématique pour répondre au moins partiellement à ce besoin. Partant d’un ensemble de composants, cette méthodologie permet de générer automatiquement tous les graphes d’architectures possibles en utilisant la technique de programmation par contraintes. Une représentation dédiée est développée pour visualiser ces graphes. Les éléments de boites de vitesse (embrayages, synchroniseurs) sont représentés avec un niveau de détails approprié pour générer de nouvelles transmission mécaniques sans trop complexifier le problème. Les graphes obtenus sont ensuite transformés en d’autres types de représentation : 0ABC Table (décrivant les connections mécaniques entre les composants), Modes Table (décrivant les modes de fonctionnement disponibles dans les architectures) et Modes Table + (décrivant pour chaque mode le rendement et le rapport de réduction global des chemins de transfert de l’énergie entre tous les composants). Sur la base de cette représentation, les nombreuses architectures générées sont filtrées et seules les plus prometteuses sont sélectionnées. Elles sont ensuite automatiquement évaluées et optimisées avec un modèle général spécifiquement développé pour calculer les performances et la consommation de toute les architectures générées. Ce modèle est inséré dans un processus d’optimisation à deux niveaux ; un algorithme génétique GA est utilisé pour le dimensionnement des composants et la programmation dynamique est utilisée au niveau contrôle (gestion de l’énergie) du système. Un cas d’étude est ensuite réalisé pour montrer le potentiel de cette méthodologie. Nous générons ainsi automatiquement toutes les architectures qui incluent un ensemble de composants défini à l’avance, et le filtrage automatique élimine les architectures présupposées non efficaces et sélectionnent les plus prometteuses pour l’optimisation. Les résultats montrent que la méthodologie proposée permet d’aboutir à une architecture meilleure (consommation diminuée de 5%) que celles imaginées de prime abord (en dehors de toute méthodologie)

Artificial intelligence is rich in algorithms for optimal control. These generate commands for dynamical systems in order to minimize a a given cost function describing the energy of the system, for example. These methods are applicable to large classes of non-linear systems in discrete time and have proven themselves in many applications. Their application in control problems is therefore very promising. However, a fundamental question remains to be clarified for this purpose: that of stability. Indeed, these studies focus on optimality and ignore in the In most cases the stability of the controlled system, which is at the heart of control theory. The objective of my thesis is to study the stability of non-linear systems controlled by such algorithms. The stakes are high because it will create a new bridge between artificial intelligence and control theory. Stability informs us about the behaviour of the system as a function of time and guarantees its robustness in the presence of model disturbances or uncertainties. Algorithms in artificial intelligence focus on control optimality and do not exploit the properties of the system dynamics. Stability is not only desirable for the reasons mentioned above, but also for the possibility of using it to improve these intelligence algorithms artificial. My research focuses on control techniques from (approximated) dynamic programming when the system model is known. For this purpose, I identify general conditions by which it is possible to guarantee the stability of the closed-loop system. On the other hand, once stability has been established, we can use it to drastically improve the optimality guarantees of literature. My work has focused on two main areas. The first concerns the approach by iteration on values, which is one of the pillars of dynamic programming is approached and is at the heart of many reinforcement learning algorithms. The second concerns the approach by optimistic planning, applied to switched systems. I adapt the optimistic planning algorithm such that, under natural assumptions in an a stabilisation context, we obtain the stability of closed-loop systems where inputs are generated by this modified algorithm, and to drastically improve the optimality guarantees of the generated inputs., L’intelligence artificielle est riche en algorithmes de commande optimale. Il s’agit de générer des entrées de commande pour des systèmes dynamiques afin de minimiser une fonction de coût donnée décrivant l’énergie du système par exemple. Ces méthodes sont applicables à de larges classes de systèmes non-linéaires en temps discret et ont fait leurs preuves dans de nombreuses applications. Leur exploitation en automatique s’avère donc très prometteuse. Une question fondamentale reste néanmoins à élucider pour cela: celle de la stabilité. En effet, ces travaux se concentrent sur l’optimalité et ignorent dans la plupart des cas la stabilité du système commandé, qui est au coeur de l’automatique. L’objectif de ma thèse est d’étudier la stabilité de systèmes non-linéaires commandés par de tels algorithmes. L’enjeu est important car cela permettra de créer un nouveau pont entre l’intelligence artificielle et l’automatique. La stabilité nous informe sur le comportement du système en fonction du temps et garantit sa robustesse en présence de perturbations ou d’incertitudes de modèle. Les algorithmes en intelligence artificielle se concentrent sur l’optimalité de la commande et n’exploitent pas les propriétés de la dynamique du système. La stabilité est non seulement désirable pour les raisons auparavant, mais aussi pour la possibilité de l’exploitée pour améliorer ces algorithmes d’intelligence artificielle. Mes travaux de recherche se concentrent sur les techniques de commande issues de la programmation dynamique (approchée) lorsque le modèle du système est connu. J’identifie pour cela des conditions générales grâce auxquelles il est possible de garantir la stabilité du système en boucle fermée. En contrepartie, une fois la stabilité établie, nous pouvons l’exploiter pour améliorer drastiquement les garanties d’optimalité de la littérature. Mes travaux se sont concentrés autour de deux axes. Le premier concerne l’approche par itération sur les valeurs, qui est l’un des piliers de la programmation dynamique approchée et est au coeur de nombre d’algorithmes d’apprentissage par renforcement. Le deuxième concerne l’approche de planification optimiste, appliqué aux systèmes commutés. J’adapte l’algorithme de planification optimiste pour que, sous hypothèse naturel dans un contexte de stabilisation, obtenir la stabilité en boucle fermé et améliorer drastiquement les garanties d’optimalité de l’algorithme.

International audience; Clustering is a fundamental problem in data science, yet, the variety of clusteringmethods and their sensitivity to parameters make clustering hard. To analyze the stability of agiven clustering algorithm while varying its parameters, and to compare clusters yielded by differentalgorithms, several comparison schemes based on matchings, information theory and various indices(Rand, Jaccard) have been developed. We go beyond these by providing a novel class of methodscomputing meta-clusters within each clustering– a meta-cluster is a group of clusters, togetherwith a matching between these.Let the intersection graph of two clusterings be the edge-weighted bipartite graph in which thenodes represent the clusters, the edges represent the non empty intersection between two clus-ters, and the weight of an edge is the number of common items. We introduce the so-calledD-family-matching problem on intersection graphs, withDthe upper-bound on the diameter ofthe graph induced by the clusters of any meta-cluster. First we prove NP-completeness resultsand unbounded approximation ratio of simple strategies. Second, we design exact polynomial timedynamic programming algorithms for some classes of graphs (in particular trees). Then, we provespanning-tree based efficient algorithms for general graphs.Our experiments illustrate the role ofDas a scale parameter providing information on the rela-tionship between clusters within a clustering and in-between two clusterings. They also show theadvantages of our built-in mapping over classical cluster comparison measures such as the variationof information (VI); Le clustering est une tâche essentielle en analyse de données, mais la variété desméthodes disponibles rend celle-ci ardue. Diverses stratégies ont été proposées pour analyserla stabilité d’un clustering en fonction des paramètres de l’algorithme l’ayant généré, ou biencomparer des clusterings produits par des algorithmes différents. Nous allons au delà de celles-ci,en proposant une nouvelle classe de méthodes formant des groupes de clusters (meta-clusters)dans chaque clustering, et établissant une correspondance entre ceux-ci.Plus spécifiquement, définissons le graphe intersection de deux clusterings comme le graphe bi-parti dont les sommets sont les clusters, chaque arête étant pondérée par le nombre de points com-muns à deux clusters. Nous définissons leD-family-matching problème à partir du graphe inter-section,Détant une borne supérieure sur le diamètre du graphe induit par les clusters des meta-clusters. Dans un premier temps, nous établissons des résultats de difficulté et d’inaproximabilité.Dans un second temps, nous développons des algorithmes de programmation dynamique pourcertaines classes de graphes (arbres en particulier). Enfin, nous concevons des algorithmes effi-caces, basés sur des arbres couvrants, pour des graphes généraux.Nos résultats expérimentaux illustrent le rôle deDcomme un paramètre d’échelle fournissantde l’information sur la relation entre les clusters intra ou inter clusterings. Ils montrent aussi lesavantages de notre appariement sur les outils de comparaison de clusterings classiques comme lavariation d’information (VI).

Que ce soit pour aller au travail, faire du magasinage ou participer à des activités sociales, la mobilité fait partie intégrante de la vie quotidienne. Nous bénéficions à cet égard d'un nombre grandissant de moyens de transports, ce qui contribue tant à notre qualité de vie qu'au développement économique. Néanmoins, la demande croissante de mobilité, à laquelle s'ajoutent l'expansion urbaine et l'accroissement du parc automobile, a également des répercussions négatives locales et globales, telles que le trafic, les nuisances sonores, et la dégradation de l'environnement. Afin d'atténuer ces effets néfastes, les autorités cherchent à mettre en oeuvre des politiques de gestion de la demande avec le meilleur résultat possible pour la société. Pour ce faire, ces dernières ont besoin d'évaluer l'impact de différentes mesures. Cette perspective est ce qui motive le problème de l'analyse et la prédiction du comportement des usagers du système de transport, et plus précisément quand, comment et par quel itinéraire les individus décident de se déplacer. Cette thèse a pour but de développer et d'appliquer des modèles permettant de prédire les flux de personnes et/ou de véhicules dans des réseaux urbains comportant plusieurs modes de transport. Il importe que de tels modèles soient supportés par des données, génèrent des prédictions exactes, et soient applicables à des réseaux réels. Dans la pratique, le problème de prédiction de flux se résout en deux étapes. La première, l'analyse de choix d'itinéraire, a pour but d'identifier le chemin que prendrait un voyageur dans un réseau pour effectuer un trajet entre un point A et un point B. Pour ce faire, on estime à partir de données les paramètres d'une fonction de coût multi-attribut représentant le comportement des usagers du réseau. La seconde étape est celle de l'affectation de trafic, qui distribue la demande totale dans le réseau de façon à obtenir un équilibre, c.-à-d. un état dans lequel aucun utilisateur ne souhaite changer d'itinéraire. La difficulté de cette étape consiste à modéliser la congestion du réseau, qui dépend du choix de route de tous les voyageurs et affecte simultanément la fonction de coût de chacun. Cette thèse se compose de quatre articles soumis à des journaux internationaux et d'un chapitre additionnel. Dans tous les articles, nous modélisons le choix d'itinéraire d'un individu comme une séquence de choix d'arcs dans le réseau, selon une approche appelée modèle de choix d'itinéraire récursif. Cette méthodologie possède d'avantageuses propriétés, comme un estimateur non biaisé et des procédures d'affectation rapides, en évitant de générer des ensembles de chemins. Néanmoins, l'estimation de tels modèles pose une difficulté additionnelle puisqu'elle nécessite de résoudre un problème de programmation dynamique imbriqué, ce qui explique que cette approche ne soit pas encore largement utilisée dans le domaine de la recherche en transport. Or, l'objectif principal de cette thèse est de répondre des défis liés à l'application de cette méthodologie à des réseaux multi-modaux. La force de cette thèse consiste en des applications à échelle réelle qui soulèvent des défis computationnels, ainsi que des contributions méthodologiques. Le premier article est un tutoriel sur l'analyse de choix d'itinéraire à travers les modèles récursifs susmentionnés. Les contributions principales sont de familiariser les chercheur.e.s avec cette méthodologie, de donner une certaine intuition sur les propriétés du modèle, d'illustrer ses avantages sur de petits réseaux, et finalement de placer ce problème dans un contexte plus large en tissant des liens avec des travaux dans les domaines de l'optimisation inverse et de l'apprentissage automatique. Deux articles et un chapitre additionnel appartiennent à la catégorie de travaux appliquant la méthodologie précédemment décrite sur des réseaux réels, de grande taille et multi-modaux. Ces applications vont au-delà des précédentes études dans ce contexte, qui ont été menées sur des réseaux routiers simples. Premièrement, nous estimons des modèles de choix d'itinéraire récursifs pour les trajets de cyclistes, et nous soulignons certains avantages de cette méthodologie dans le cadre de la prédiction. Nous étendons ensuite ce premier travail afin de traiter le cas d'un réseau de transport public comportant plusieurs modes. Enfin, nous considérons un problème de prédiction de demande plus large, où l'on cherche à prédire simultanément l'enchaînement des trajets quotidiens des voyageurs et leur participation aux activités qui motivent ces déplacements. Finalement, l'article concluant cette thèse concerne la modélisation d'affectation de trafic. Plus précisément, nous nous intéressons au calcul d'un équilibre dans un réseau où chaque arc peut posséder une capacité finie, ce qui est typiquement le cas des réseaux de transport public. Cet article apporte d'importantes contributions méthodologiques. Nous proposons un modèle markovien d'équilibre de trafic dit stratégique, qui permet d'affecter la demande sur les arcs du réseau sans en excéder la capacité, tout en modélisant comment la probabilité qu'un arc atteigne sa capacité modifie le choix de route des usagers., Traveling is an essential part of daily life, whether to attend work, perform social activities, or go shopping among others. We benefit from an increasing range of available transportation services to choose from, which supports economic growth and contributes to our quality of life. Yet the growing demand for travel, combined with urban sprawl and increasing vehicle ownership rates, is also responsible for major local and global externalities, such as degradation of the environment, congestion and noise. In order to mitigate the negative impacts of traveling while weighting benefits to users, transportation planners seek to design policies and improve infrastructure with the best possible outcome for society as a whole. Taking effective actions requires to evaluate the impact of various measures, which necessitates first to understand and predict travel behavior, i.e., how, when and by which route individuals decide to travel. With this background in mind, this thesis has the objective of developing and applying models to predict flows of persons and/or vehicles in multi-modal transportation networks. It is desirable that such models be data-driven, produce accurate predictions, and be applicable to real networks. In practice, the problem of flow prediction is addressed in two separate steps, and this thesis is concerned with both. The first, route choice analysis, is the problem of identifying the path a traveler would take in a network. This is achieved by estimating from data a parametrized cost function representing travelers' behavior. The second step, namely traffic assignment, aims at distributing all travelers on the network's paths in order to find an equilibrium state, such that no traveler has an interest in changing itinerary. The challenge lies in taking into account the effect of generated congestion, which depends on travelers' route choices while simultaneously impacting their cost of traveling. This thesis is composed of four articles submitted to international journals and an additional chapter. In all the articles of the thesis, we model an individual's choice of path as a sequence of link choices, using so-called recursive route choice models. This methodology is a state-of-the-art framework which is known to possess the advantage of unbiased parameter estimates and fast assignment procedures, by avoiding to generate choice sets of paths. However, it poses the additional challenge of requiring one to solve embedded dynamic programming problems, and is hence not widely used in the transportation community. This thesis addresses practical and theoretical challenges related to applying this methodological framework to real multi-modal networks. The strength of this thesis consists in large-scale applications which bear computational challenges, as well as some methodological contributions to this modeling framework. The first article in this thesis is a tutorial on predicting and analyzing path choice behavior using recursive route choice models. The contribution of this article is to familiarize researchers with this methodology, to give intuition on the model properties, to illustrate its advantages through examples, and finally to position this modeling framework within a broader context, by establishing links with recently published work in the inverse optimization and machine learning fields. Two articles and an additional chapter can be categorized as applications of the methodology to estimate parameters of travel demand models in several large, real, and/or multi-dimensional networks. These applications go beyond previous studies on small physical road networks. First, we estimate recursive models for the route choice of cyclists and we demonstrate some advantages of the recursive models in the context of prediction. We also provide an application to a time-expanded public transportation networks with several modes. Then, we consider a broader travel demand problem, in which decisions regarding daily trips and participation in activities are made jointly. The latter is also modeled with recursive route choice models by considering sequences of activity, destination and mode choices as paths in a so-called supernetwork. Finally, the subject of the last article in this thesis is traffic assignment. More precisely, we address the problem of computing a traffic equilibrium in networks with strictly limited link capacities, such as public transport networks. This article provides important methodological contributions. We propose a strategic Markovian traffic equilibrium model which assigns flows to networks without exceeding link capacities while realistically modeling how the risk of not being able to access an arc affects route choice behavior.

This PhD thesis proposes Energy Management Strategies conceived for a hybrid electrical urban bus. The hybrid control system should create an efficient strategy of coordinating the flow of energy between the heat engine, battery, electrical and hydraulic motors. Firstly, a Deterministic Dynamic Programming (DDP) based approach has been proposed: simultaneous speed and powersplit optimization algorithm for a given trip (constrained by the traveled distance and time limit). This algorithm turned out to be highly time consuming so it cannot be used in real-time. To overcome this drawback, an Optimal Profiles Database based on DP (OPD-DP) has been constructed for real-time application. Afterwards, a Stochastic Dynamic Programming (SDP) technique is used to simultaneously generate an optimal speed profile and related powersplit strategy. This approach takes into account a stochastic nature of the driving behavior and urban conditions. The formulated energy optimization problem, being intrinsically multi-objective problem, has been transformed into several single-objective ones with constraints using an ε-constraint method to determine a set of optimal solutions (the Pareto Front).In urban environment, due to traffic conditions, traffic lights, a bus encounters frequent Stop&Go situations. This results in increased energy consumption during the starts. In this sense, a relevant Eco Adaptive Cruise Control with Stop&Go (eACCwSG) strategy brings the undeniable benefit. The algorithm smooths speed profile during acceleration and braking phases. One more important feature of this algorithm is the safety aspect, as eACCwSG permits to maintain a safety distance in order to avoid collision and apply a smooth braking. As it was mentioned before, smooth braking ensures passengers comfort., Cette thèse propose des stratégies de gestion de l'énergie conçues pour un bus urbain électrique hybride. Le système de commande hybride devrait créer une stratégie efficace de coordination du flux d’énergie entre le moteur thermique, la batterie, les moteurs électriques et hydrauliques. Tout d'abord, une approche basée sur la programmation dynamique déterministe (DDP) a été proposée : algorithme d'optimisation simultanée de la vitesse et de la puissance pour un trajet donné (limité par la distance parcourue et le temps de parcours). Cet algorithme s’avère être gourmand en temps de calcul, il n’a pas été donc possible de l’utiliser en temps réel. Pour remédier à cet inconvénient, une base de données de profils optimaux basée sur DP (OPD-DP) a été construite pour une application en temps réel. Ensuite, une technique de programmation dynamique stochastique (SDP) a été utilisée pour générer simultanément et d’une manière optimale un profil approprié de la vitesse du Bus ainsi que sa stratégie de partage de puissance correspondante. Cette approche prend en compte à la fois la nature stochastique du comportement de conduite et les conditions de circulations urbaines (soumises à de multiples aléas). Le problème d’optimisation énergétique formulé, en tant que problème intrinsèquement multi-objectif, a été transformé en plusieurs problèmes à objectif unique avec contraintes utilisant une méthode ε-constraint afin de déterminer un ensemble de solutions optimales (le front de Pareto).En milieu urbain, en raison des conditions de circulation, des feux de circulation, un bus rencontre fréquemment des situations Stop&Go. Cela se traduit par une consommation d'énergie accrue lors notamment des démarrages. En ce sens, une stratégie de régulation de vitesse adaptative adaptée avec Stop&Go (eACCwSG) apporte un avantage indéniable. L'algorithme lisse le profil de vitesse pendant les phases d'accélération et de freinage du Bus. Une autre caractéristique importante de cet algorithme est l’aspect sécurité, étant donné que l’ACCwSG permet de maintenir une distance de sécurité afin d’éviter les collisions et d’appliquer un freinage en douceur. Comme il a été mentionné précédemment, un freinage en douceur assure le confort des passagers.

International audience; Les réseaux SDN (software-defined networking) permettent d'optimiser globalement la configuration des réseaux en fonction du trafic. Idéalement, le réseau devrait être reconfiguré de manière dynamique afin de permettre une meilleure utilisation des ressources. Néanmoins, en pratique, les changements de routes ne peuvent pas être trop fréquents à cause de la lente mise à jour des équipements et de la dynamicité individuelle des flux. Pour trouver un bon compromis entre fréquence de reconfiguration et l'efficacité de l'utilisation des ressources, une nouvelle approche d'ingénierie de trafic basée sur le clustering robuste a été proposée dans [SFC + 18]. L'idée principale est de regrouper des scénarios de trafic futurs présentants des similitudes de routage et temporel. Pour résoudre le problème de clustering robuste d'une manière optimale et rapide, nous proposons un nouvel algorithme basé sur la programmation dynamique. Nous comparons l'algorithme avec l'approche heuristique de [SFC + 18] et la résolution de l'ILP sur des instances réelles. Les résultats montrent que notre approche est efficace pour trouver la solution optimale et améliore les performances du routage par rapport à l'heuristique. Mots-clefs : Réseaux logiciels, routage robuste, calcul de chemins, programmation dynamique

Les trains à empilement double sont une composante majeure du réseau de transport ferroviaire pour les conteneurs intermodaux dans certains marchés comme celui de l’Amérique du Nord. Le séquençage du chargement représente un problème opérationnel auquel font face les opérateurs de grues dans les cours de chargement lorsqu’ils ont pour tâche de placer les conteneurs sur un train. Le séquençage du chargement consiste à trouver une séquence de mouvements permettant d’extraire les conteneurs des piles dans lesquels ils sont entreposés afin de les placer sur le train. Le séquençage du chargement est interrelié avec la planification du chargement, processus dans lequel des conteneurs sont assignés à des placements spécifiques sur les wagons, afin de former un plan de chargement pour guider le séquençage. Le travail dans ce mémoire s’articule autour d’un article scientifique sur l’optimisation du séquençage du chargement pour les trains à empilement double. Dans cet article sont présentés des algorithmes basés sur la programmation dynamique, ainsi qu’une stratégie tirant avantage de plans de chargement développés afin de solutionner le séquençage pour des instances de chargement réalistes. Les résultats montrent que les heuristiques suggérées fonctionnent bien même pour des instances de grande taille. Ces dernières présentent une légère perte en qualité des solutions mais un temps d’exécution nettement inférieur aux méthodes exactes faisant défaut pour des instances de grande taille. L’analyse démontre également que l’utilisation de plans de chargement plus flexibles permet d’améliorer la qualité des solutions avec toutes les méthodes, ceci se faisant au coût d’un temps d’éxecution supérieur et l’absence d’une garantie de solution pour les heuristiques. Finalement, la planification et le séquençage simultané sont comparés avec l’approche successive utilisant les algorithmes developpés afin d’évaluer la performance relative des deux approches., Double-stack trains are an important component of the railroad transport network for containerized cargo in specific markets such as the North American one. The load sequencing is an operational problem commonly faced in rail terminals by crane operators when tasked with loading containers on the railcars of a train. The load sequencing problem aims to find an efficient sequence of container retrievals in the storage yard, where containers are stored in piles while awaiting departure by train. Load sequencing is interrelated with load planning, the assignment of containers to specific locations on the train, forming a load plan which guides the load sequencing. The work in this thesis is centered around a scientific paper on the optimization of load sequencing for double-stack trains. This paper proposes algorithms based on dynamic programming and a strategy leveraging the load plans, and assesses their performance in terms of computing time, tractability and solution quality on realistic instance sizes. The results show that the heuristics suggested to solve the load sequencing scale well for realistic instance size, managing to achieve a significantly reduced computing time with a small loss in solution quality compared to exact methods, which would often falter for larger instances. The analysis also illustrates how using a flexible load plan in the load sequencing significantly improves solution quality at the cost of greater computing requirements and lack of guaranteed solution for the heuristics. Finally, the paper compares the performance resulting from the successive application of load planning and sequencing with jointly performing the load planning and sequencing.

Sampling methods are central to many algorithmic methods in structural RNA bioinformatics, where they are routinely used to identify important structural models, provide summarized pictures of the folding landscapes, or approximate quantities of interest at the thermodynamic equilibrium.In all of these examples, redundancy within sampled sets is uninformative and computationally wasteful, limiting the scope of application of existing methods.In this thesis, we introduce the concept of non-redundant sampling, and explore its applications and consequences in RNA bioinformatics.We begin by formally introducing the concept of non-redundant sampling and demonstrate that any algorithm sampling in Boltzmann distribution can be modified into non-redundant variant. Its implementation relies on a specific data structure and a modification of the stochastic backtrack to return the set of unique structures, with the same complexity.We then show a practical example by implementing the non-redundant principle into a combinatorial algorithm that samples locally optimal structures. We use this tool to study the RNA kinetics by modeling the folding landscapes generated from sets of locally optimal structures. These structures act as kinetic traps, influencing the outcome of the RNA kinetics, thus making their presence crucial. Empirical results show that the landscapes generated from the non-redundant samples are closer to the reality than those obtained by classic approaches.We follow by addressing the problem of the efficient computation of the statistical estimates from non-redundant sampling sets. The absence of redundancy means that the naive estimator, obtained by averaging quantities observed in a sample, is erroneous. However we establish a non-trivial unbiased estimator specific to a set of unique Boltzmann distributed secondary structures. We show that the non-redundant sampling estimator performs better than the naive counterpart in most cases, specifically where most of the search space is covered by the sampling.Finally, we introduce a sampling algorithm, along with its non-redundant counterpart, for secondary structures featuring simple-type pseudoknots. Pseudoknots are typically omitted due to complexity reasons, yet many of them have biological relevance. We begin by proposing a dynamic programming scheme that allows to enumerate all recursive pseudoknots consisting of two crossing helices, possibly containing unpaired bases. This scheme generalizes the one proposed by Reeders and Giegerich, chosen for its low time and space complexities. We then explain how to adapt this decomposition into a statistical sampling algorithm for simple pseudoknots. We then present preliminary results, and discuss about extensions of the non-redundant principle in this context.The work presented in this thesis not only opens the door towards kinetics analysis for longer RNA sequences, but also more detailed structural analysis of RNAs in general. Non-redundant sampling can be applied to analyze search spaces for combinatorial problems amenable to statistical sampling, including virtually any problem solved by dynamic programming. Non-redundant sampling principles are robust and typically easy to implement, as demonstrated by the inclusion of non-redundant sampling in recent versions of the popular Vienna package.; Un échantillonnage statistique est central à de nombreuses méthodes algorithmiques pour la bioinformatique structurale des ARNs, où ils sont couramment utilisés pour identifier des modèles structuraux importants, fournir des résumés des espaces de repliement ou approcher des quantités d'intérêt dans l'équilibre thermodynamique. Dans tous ces exemples, la redondance dans l'ensemble échantillonné est non-informative et inefficace, limitant la portée des applications des méthodes existantes. Dans cette thèse, nous introduisons le concept de l'échantillonnage non-redondante et nous explorons ses applications et conséquences en bioinformatique des ARN.Nous commençons par introduire formellement le concept d'échantillonnage non-redondante et nous démontrons que tout algorithme échantillonnant dans la distribution de Boltzmann peut être modifié en une version non-redondante. Son implémentation repose sur une structure de données spécifique et la modification d'une remontée stochastique pour fournir l'ensemble des structures uniques, avec la même complexité.Nous montrons alors une exemple pratique en implémentant le principe d'échantillonnage non-redondant au sein d'un algorithme combinatoire qui échantillonne des structures localement optimales. Nous exploitons cet outil pour étudier la cinétique des ARN, modélisant des espaces de repliement générés à partir des structures localement optimales. Ces structures agissent comme des pièges cinétiques, rendant leur prise en compte essentielle pour analyser la dynamique des ARN. Des résultats empirique montrent que des espaces de repliement générés à partir des échantillons non-redondants sont plus proches de la réalité que ceux obtenus par un échantillonnage classique.Nous considérons ensuite le problème du calcul efficace d'estimateurs statistiques à partir d'échantillons non redondants. L'absence de la redondance signifie que l'estimateur naïf, obtenu en moyennant des quantités observés dans l'échantillon, est erroné. Par contre, nous établissons un estimateur non-trivial non-biaisé spécifique aux échantillons non-redondants suivant la distribution de Boltzmann. Nous montrons que l'estimateur des échantillons non-redondants est plus efficace que l'estimateur naïf, notamment dans les cas où la majorité des l'espace de recherche est échantillonné.Finalement, nous introduisons l'algorithme d'échantillonnage, avec sa contre-partie non-redondante, pour des structures secondaires présentant des pseudonoeuds de type simple. Des pseudonoeuds sont typiquement omis pour des raisons d'efficacité, bien que beaucoup d'entre eux possèdent une grande importance biologique. Nos commençons par proposer une schéma de programmation dynamique qui permet d'énumérer tous les pseudonoeuds composés de deux hélices pouvant contenir des bases non-appariés qui s'entrecroisent. Ce schéma généralise la proposition de Reeders et Giegerich, choisi pour sa base complexité temporelle et spatiale. Par la suite, nous expliquons comment adapter cette décomposition à un algorithme d'échantillonnage statistique pour des pseudonoeuds simples. Finalement, nous présentons des résultats préliminaires et nous discutons sur l'extension de principe non-redondant dnas ce contexte.Le travail présenté dans cette thèse ouvre non seulement la porte à l'analyse cinétique des séquences d'ARN plus longues, mais aussi l'analyse structurale plus détaillée des séquences d'ARN en général. L'échantillonnage non-redondant peut être employé pour analyser des espaces de recherche pour des problèmes combinatoires susceptibles à l'échantillonnage statistique, y inclus virtuellement tous problèmes solvables par la programmation dynamique. Les principes d'échantillonnage non-redondant sont robustes et typiquement faciles à implémenter, comme démontré par l'inclusion d'échantillonnage non-redondant dans les versions récentes de Vienna package populaire.

International audience; Présentation du problème et programme linéaire en variables mixtes Ce papier traite d'un problème d'ordonnancement d'un ensemble A de tâches préemptives, sur un horizon T discrétisé en périodes. Chaque tâche doit être exécutée à l'intérieur d'une fenêtre temporelle [r i , d i [ sur une durée p i , ∀i ∈ A, et consommatrices d'électricité selon une demande individuelle b i sur chaque période d'exécution de la tâche. L'énergie demandée par l'ensemble des tâches dans une période est la somme des énergies demandées individuellement par les tâches. Elle peut être apportée au moyen de deux sources d'énergie. Une source d'énergie réversible, de type batterie, peut stocker et restituer de l'énergie avec un stock initial s 0 et une capacité de stockage Q. Une source d'énergie non-réversible, de type fournisseur d'électricité, ne peut que fournir de l'énergie moyennant un coût linéaire par morceaux dépendant du temps ρ t (b) à payer sur chaque période de temps t pour une consommation totale b. Dans un travail précédent nous avons proposé des approches de programmation linéaire en nombres entiers pour un problème (ORDO) similaire mais sans source réversible. Nous avons montré que le problème était déjà NP-difficile au sens fort et proposé un algorithme de Branch & Price (BP) pour le résoudre efficacement [2]. A l'inverse, lorsque l'ordonnancement des tâches est fixé, on obtient une demande énergétique prédéterminée. Le problème de couverture de la demande de chaque période par les deux sources est équivalent à un problème de lot-sizing (LS), NP-difficile au sens faible. Un algorithme de programmation dynamique (PD) en O(|T | 2qd) a été proposé pour des demandes entières oùd désigne la demande moyenne etq est le nombre moyen de points de rupture de la fonction ρ. Un programme linéaire en variables mixtes (PLVM) de taille pseudo-polynomiale peut être proposé en utilisant les variables de décisions binaires x it , ∀i ∈ A, t ∈ T signifiant que la tâche i est en cours d'exécution à la période t. Une variable continue s t ≥ 0 donne le stock dans la ressource réversible à la période t et une variable continue w t donne la quantité d'énergie fournie par la source non-réversible à la période t. Avec ces variables on doit minimiser la fonction t∈T ρ t (w t). Une contrainte de respect des durées s'écrit di−1 t=ri x it ≥ p i , ∀i ∈ A. Le respect dans la demande et l'allocation d'énergie pour toute période t ∈ T s'écrit w t − i∈A b i x it + s t−1 − s t = 0. On impose par ailleurs que le stock initial soit restitué (s |T | ≥ s 0) et que le stock ne dépasse pas la capacité (s t ≤Q, ∀t ∈ T). Enfin on pose x it = 0 pour tout t ∈ [t i , d i [. Matheuristique Le PLVM montre ses limites et ne parvient pas à résoudre optimalement plusieurs instances à 30 et 60 tâches en moins de 600s. Or comme nous disposons de méthodes exactes efficaces pour résoudre exactement (ORDO) et (LS) séparément, nous proposons une matheuristique

International audience; Ce papier étudie le problème du séquencement des avions lors de leur arrivée à l'aéroport, problème connu dans la littérature sous le nom de Aircraft Landing Problem [1]. Il s'agit de séquencer les avions arrivant sur la piste d'atterrissage tout en respectant des conditions de sécurité entre les avions. Les avions créent des turbulences et une durée minimum entre deux atterrissages successifs doit être respectée. La durée de séparation dépend du type des avions qui se suivent. Un petit avion qui atterrit derrière un gros avion doit attendre plus longtemps qu'un gros avion qui atterrit à la suite d'un petit. Chaque avion $i$ peut atterrir dans une certaine fenêtre de temps $[E_i , L_i ]$. $E_i$ est la date au plus tôt à laquelle l'avion peut atterrir, $L_i$ est la date au plus tard. Dans cette fenêtre, $T_i$ est la date préférée d'atterrissage qui correspond à la date à laquelle l'avion arriverait sur la piste s'il allait à sa vitesse de croisière. Si l'avion $i$ était seul il atterrirait à la date $T_i$ mais en présence d'autres avions un arbitrage est nécessaire. Les avions doivent soit accélérer pour atterrir plus tôt ou au contraire ralentir voire faire des boucles pour arriver plus tard afin de respecter les contraintes de sécurité. Une déviation par rapport à la date préférée d'atterrissage engendre un coût. Dans la littérature on considère généralement qu'une avance ou un retard engendre un coût linéaire en fonction de l'écartement à la date préférée d'atterrissage. L'objectif est de minimiser le coût total de déviation. Sur chaque piste, le problème se décompose en deux phases : d'abord choisir l'ordre des avions et ensuite calculer les dates d'atterrissage. Ce dernier problème peut se résoudre par un PL (Programme Linéaire) [3, 5, 6, 7]. A. Faye [4] propose un algorithme de complexité quadratique en fonction du nombre d'avions. Cependant, un coût linéaire peut s'avérer assez éloigné des coûts réels encourus. Par exemple, un retard peut avoir des conséquences sur les passagers en correspondance et sur les vols ultérieurs sur lesquels le personnel de bord devra prendre place. On conçoit facilement que plus le retard est grand, plus les complications sont nombreuses et que plus l'impact sur le coût s'accroît. Il est donc légitime de modéliser la fonction coût par une fonction convexe et affine par morceaux centrée en la date préférée d'atterrissage et avec des pentes croissantes de part et d'autre de cette date. Pour des raisons d'équité entre compagnies aériennes, une fonction de ce type a été introduite par Soomer et Franx [6]. Pour un ordre fixé des avions, le coût total était calculé par un PL. Ici, nous proposons un algorithme polynomial dont la complexité dépend à la fois du nombre d'avions et du nombre de pentes de la fonction de coût d'un avion. Ainsi, si n est le nombre d'avions et si b est le nombre maximum de pentes que peut comporter le coût d'un avion, la complexité de l'algorithme est $O(n^2 b^2)$. Cet algorithme est basé sur la programmation dynamique et est une généralisation de l'algorithme proposé dans [4].