Le reformage autothermique, dans lequel une oxydation air carburant permet d’initier les réactions de formation d’hydrogène à partir de carburant et d’eau, semble une voie prometteuse pour la synthèse d’hydrogène à bord de navires. Son application au diesel, carburant majoritairement utilisé dans le secteur maritime, bien que moins bien connue académiquement que celle du méthane, permet une opérabilité du vaisseau sur l’ensemble du globe. Cependant les réacteurs associés sont particulièrement sujets au dépôt de carbone, néfaste pour leur durabilité, et requièrent alors une attention toute particulière au niveau des zones de mélange lors de leur conception. Dans les cas d’écoulements fortement tridimensionnels, une approche RANS couplée à un schéma cinétique décrivant les espèces gazeuses, est le plus souvent utilisée. Ce schéma consiste alors soit en un nombre succint de réactions empiriques, au risque de se montrer peu précis sur les niveaux de polluants, ou au contraire en des schémas d’une cinquantaine d’espèces issus de la réduction automatique de schémas complets, qui restent cependant trop lourds à utiliser lors d’une phase de conception. L’objectif de la thèse est alors de proposer une méthodologie pour décrire l’impact d’une géométrie sur les niveaux de polluants compatibles avec les outils habituellement utilisés dans le milieu industriel. Ainsi, la description du couplage chimie-écoulement est réalisée par le biais des logiciels Fluent R et de la suite Chemkin R de ANSYS R . Après une analyse de la chimie du reformage autothermique du diesel, une méthode de génération de schémas globaux d’une di-zaine d’espèces à partir d’un schéma détaillé est proposée. Elle est, par la suite appliquée avec succès à l’oxydation partielle du n-dodécane. Le schéma estalors utilisé dans la première simulation réactive de reformeur auto-thermique avec injection de diesel liquide réalisée à ce jour. Malgré les difficultés de validation dûes au manque de données experimentales et aux limitations des logiciels imposés, les résultats obtenus sont encourageants. / Autothermal reformers use fuel-air oxidation to ensure production of hydrogen from fuel and water on-board. The use of diesel instead of better-known methan, permits the ships to be refuelled all around the world. These systems show strong sensitivity to carbon deposit which reduces their lifetime. Good knowledge of the fuel air mixing is thus required. Academic description of such tridimensional systems usually relies on the application of a RANS simulation coupled with gaseous chemical kinetics mechanism. These mechanisms can then consist on a few empirical reactions, or at the opposite, on quite large schemes, with more than 50 species derived automatically from big detailled schemes. The resulting description is then not enough precise, or at the opposite too computationally expensive to be used during design process. This thesis thus aims to develop an industrial compatible methodology to describe the impact of design geometry on pollutant formation. ANSYS software such as Fluent and Chemkin are then used to perform the simulation. An original method of limited size mechanism derivation from larger chemical scheme is proposed. It is succesfully applied to the generation of a partial oxidation mechanism of n-dodecane, from the results of diesel reforming chemical analysis. The resulting scheme is then applied on theliquid injection diesel autoreformer reactive simulation. Even if validation difficulties result from the lack of experimental data and limitations of the softwares, it remains the first simulation of this kind in the litterature, to our knowledge. Promising results are obtained.

Cette thèse porte sur l'efficacité des algorithmes distribués de partage des ressources et des algorithmes de découvert de chemin en ligne. Dans la première partie de la thèse, nous analysons un jeu dans lequel les utilisateurs paient pour utiliser une ressource partagée. La ressource allouée à un utilisateur est directement proportionnel à son paiement. Chaque utilisateur veut minimiser son paiement en assurant une certaine qualité de service. Ce problème est modélisé comme un jeu non-coopératif de partage des ressources. A cause du manque des expressions analytiques de la discipline de file d'attente sous-jacente, nous pouvons résoudre le jeu que sous certaines hypothèses. Pour le cas général, nous développons une approximation basée sur un résultat fort trafic et nous validons la précision de l'approximation numériquement.Dans la deuxième partie, nous étudions l'efficacité des jeux de balance de charge, c'est à dire, nous comparons la perte de performance de routage non coopératif décentralisé avec un routage centralisé. Nous montrons que le PoA est une mesure très pessimiste car il est atteint que dans des cas pathologiques. Dans la plupart des scénarios, les implémentations distribués de balance de charge effectuent presque aussi bien que la mise en œuvre centralisée optimale.Dans la dernière partie de la thèse, nous analysons problème de découverte chemin optimal dans les graphes complets. En ce problème, les valeurs des arêtes sont inconnues, mais peuvent être interrogés. Pour une fonction donnée qui est appliquée à des chemins, l'objectif est de trouver un meilleur chemin de valeur à partir d'une source vers une destination donnée interrogation le plus petit nombre de bords. Nous vous proposons le rapport de requête en tant que mesure de l'efficacité des algorithmes qui permettent de résoudre ce problème. Nous prouvons une limite inférieure pour ne importe quel algorithme qui résout ce problème et nous avons proposé un algorithme avec un rapport de requête strictement inférieure à 2. / This thesis deals with the efficiency of distributed resource sharing algorithms and of online path discovery algorithms. In the first part of the thesis, we analyse a game in which users pay for using a shared resource. The allocated resource to a user is directly proportional to its payment. Each user wants to minimize its payment while ensuring a certain quality of service. This problem is modelled as a non-cooperative resource-sharing game. Due to lack of analytical expressions for the underlying queuing discipline, we are able to give the solution of the game only under some assumptions. For the general case, we develop an approximation based on a heavy-traffic result and we validate the accuracy of the approximation numerically. In the second part, we study the efficiency of load balancing games, i.e., we compare the loss in performance of noncooperative decentralized routing with a centralized routing. We show that the PoA is very pessimistic measure since it is achieved in only pathological cases. In most scenarios, distributed implementations of load-balancing perform nearly as well as the optimal centralized implementation. In the last part of the thesis, we analyse the optimal path discovery problem in complete graphs. In this problem, the values of the edges are unknown but can be queried. For a given function that is applied to paths, the goal is to find a best value path from a source to a given destination querying the least number of edges. We propose the query ratio as efficiency measure of algorithms that solve this problem. We prove a lower-bound for any algorithm that solves this problem and we proposed an algorithm with query ratio strictly less than 2.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L’optimisation combinatoire concerne la résolution de problèmes pour lesquels les variables prennent des valeurs discrètes et sur lesquelles s’appliquent des contraintes. L’ensemble des variables et des contraintes définissent un modèle représentant le problème. Un très grand nombre de problèmes industriels peuvent être représentés sous cette forme. Un logiciel qui prend un modèle en entrée et produit une solution est appelé solveur. La programmation par contraintes (PPC) est l’une des techniques algorithmiques pouvant être utilisée par ces solveurs. Dans ce mémoire, nous développons un nouveau solveur. L’objectif premier est de compter sur un solveur facilement modifiable dans le but d’y ajouter de nouvelles approches de résolution développées par les chercheurs. De plus, dans le but de démontrer l’utilité du solveur, nous développons une approche exploitant ce solveur dans le but de générer des patrons de chargement alternatifs pour un séchoir à bois utilisé par l’industrie des produits forestiers. Finalement, nous présentons dans ce mémoire une nouvelle technique pour résoudre avec plus d’efficience certains problèmes de PPC. Les algorithmes de filtrage associés aux contraintes sont typiquement déclenchés en fonction d’événements qui se produisent lors de la résolution du problème. Nous proposons un nouvel événement qui permet d’effectuer du filtrage tardif des variables. Nous montrons que, pour un problème classique d’optimisation combinatoire (Balanced Incomplete Block Design), il donne une meilleure performance tout en maintenant le même niveau de filtrage par rapport à l’utilisation des événements classiques. / Combinatorial optimization concerns the solving of problems for which the variables take discrete values and on which constraints apply. The set of variables and constraints form the model of the problem. A lot of industrial problems can be represented in this form. A solver is a software that takes as input a model and produces a solution. Constraint programming (CP) is one of the algorithmic techniques that can be used within a solver. In this master’s thesis, we develop a new solver. The primary objective is to rely on an easily modifiable solver in order to add new resolution approaches developed by researchers. Moreover, in order to demonstrate the utility of the solver, we develop an approach using that solver in order to generate alternative loading patterns for a kiln in the forest industry. Finally, in this master’s thesis, we present a new technique for solving some CP problems. The filtering algorithms are triggered according to events that occur when solving the problem. We propose a new event that allows to perform a lazy filtering of the variables. We demonstrate, on a classical combinatorial optimization problem (Balanced Incomplete Block Design), that it gives a better performance while maintaining the same level of filtering when compared with classical events.

Les méthodes de Monte-Carlo multicanoniques sont des techniques adaptatives de simulation numérique permettant d'estimer des distributions de probabilités complexes, particulièrement lorsque les probabilités recherchées sont extrêmement petites. Ces méthodes sont basées notamment sur les chaînes de Markov. Avec ces méthodes il est possible d'obtenir des résultats de manière beaucoup plus rapide qu'avec d'autres techniques comme le Monte-Carlo. Nous discutons ici de la parallélisation de ces algorithmes, pour en permettre l'utilisation sur un super-ordinateur. De cette manière, il deviendra possible de simuler des systèmes encore plus complexes avec davantage de précision. Dans ce mémoire, nous voyons tout d'abord des notions de base à propos de la programmation parallèle. Puis nous étudions les fondements mathématiques du Monte-Carlo multicanonique. Ensuite, nous déterminons des critères pour en estimer la performance et la précision. Enfin, nous étudions comment on peut le paralléliser afin de l'utiliser sur un super-ordinateur.

Thèse en cotutelle : Université Laval, Québec, Canada, Philosophiæ doctor (Ph. D.) et Wuhan University, Wuhan, Chine. / Au cours des dernières décennies, l'augmentation de la production primaire (PP) dans l'océan Arctique (AO) a en partie été associée à une augmentation de la biomasse phytoplanctonique, comme l'ont montré des études de télédétection. La concentration en chlorophylle a (Chl), un indicateur de la biomasse phytoplanctonique, est un facteur clé qui peut biaiser les estimations de la PP quand elle comporte des erreurs de mesure. En d'autres mots, une estimation précise de la Chl est cruciale pour améliorer notre connaissance de l'écosystème marin et de sa réponse au changement climatique en cours. Cependant, la télédétection de la couleur de l'océan dans l'océan Arctique présente plusieurs défis. Tout d'abord, il est bien connu que l'échec des algorithmes standards de la couleur de l'océan dans l'AO est dû à l'interférence des matières colorées et détritiques (CDM) dans le spectre visible, mais comment et dans quelle mesure cela va biaiser l'estimation de la Chl reste inconnu. En outre, la Chl étant un facteur clé utilisé pour estimer la PP, la propagation des erreurs des estimations de la Chl aux estimations de la PP doit être évaluée. Le dernier mais le plus important est qu'un algorithme robuste avec une incertitude raisonnable, en particulier pour les eaux côtières complexes et productives, n'est pas encore disponible. Pour résoudre ces problèmes, dans cette étude, nous avons d'abord compilé une grande base de données bio-optiques in situ dans l'Arctique, à partir de laquelle nous avons évalué de manière approfondie les algorithmes de couleur de l'océan actuellement disponibles du point de vue des impacts des CDM. Nous avons constaté que plus le niveau de CDM par rapport à la Chl dans la colonne d'eau était élevé, plus il biaisait les estimations de la Chl. L'analyse de sensibilité des estimations de la PP sur la Chl a montré que l'erreur des estimations de la Chl était amplifiée de 7% lorsqu'elle était passée dans l'estimation du PP en utilisant un modèle de PP résolu spectralement et verticalement. En outre, pour obtenir de meilleurs résultats, nous avons optimisé un algorithme semi-analytique (Garver-Siegel-Maritorena, GSM) pour l'AO en ajoutant la bande spectrale de 620 nm qui est moins affectée par le CDM et le signal ici est généralement élevé pour les eaux riches en CDM, devenant anisi important pour le GSM afin d'obtenir des estimates précises de la Chl. Notre algorithme ajusté, GSMA, n'a amélioré la précision que de 8% pour l'AO, mais l'amélioration pour les eaux côtières a atteint 93%. Enfin, étant donné que les algorithmes qui n'exploitent pour la plupart que les parties bleue et verte du spectre visible sont problématiques pour les eaux très absorbantes/obscures, nous avons introduit un modèle d'émission de fluorescence pour tenir compte des propriétés bio-optiques du phytoplancton dans la partie rouge du spectre visible. En se couplant avec le GSMA, le nouvel algorithme à spectre complet, FGSM, a encore amélioré la précision des estimations de la Chl de ~44% pour les eaux eutrophes. À l'avenir, des couplages sont nécessaires à des fins de validation en ce qui concerne l'application satellitaire. De plus, de nouvelles approches pouvant être appliquées pour détecter le maximum de chlorophylle sous la surface (SCM), les efflorescences en bordure de glace et/ou sous la glace, les types fonctionnels de phytoplancton (PFT), sont attendues. / In the recent decades, the raise of primary production (PP) in the Arctic Ocean (AO) is mainly driven by the increase of phytoplankton biomass as multiple remote sensing studies have suggested. Chlorophyll a concentration (Chl), a proxy of phytoplankton biomass, is a key factor that biases PP estimates. In terms of bottom-up control, accurate Chl estimate is crucial to improve our knowledge of marine ecosystem and its response to ongoing climate change. However, there are several challenges of ocean color remote sensing in the Arctic Ocean. Firstly, it is well known that the failure of standard ocean color algorithms in the AO is due to the interference of colored and detrital material (CDM) in the visible spectrum, but how and to what extend it will bias the estimation of Chl remains unknown. Besides, Chl as a key factor used to estimate PP, error propagation from Chl estimates to PP estimates needs to be assessed. The last but most important is that a robust algorithm with reasonable uncertainty, especially for the complex and productive coastal waters, is not yet available. To address these problems, in this study, we first compiled a large Arctic in situ bio-optical database, based on which we thoroughly evaluated presently available ocean color algorithms from a perspective of the impacts of CDM. We found that the higher the level of CDM relative to Chl in the water column, the larger it would bias Chl estimates. Sensitivity analysis of PP estimates on Chl showed that the error of Chl estimates was amplified within 7% when passed into the estimation of PP using a spectrally- and vertically-resolved PP model. Besides, to obtain better results, we tuned GSM for the AO by adding 620 waveband which is less affected by CDM and the signal here is generally high for CDM-rich waters thus become important for GSM to retrieve accurate Chl estimates. Our tuned algorithm, GSMA, merely improved the accuracy by 8% for the AO, but the improvement for coastal waters reached up to 93%. Finally, given that algorithms that only exploits visible spectrum are problematic for highly-absorbing/dark waters, we introduced the fluorescence emission model to account for the bio-optical properties of phytoplankton in the near infrared spectrum. By coupling with GSMA, the novel full-spectrally algorithm, FGSM, further improved the accuracy of Chl estimates by ~44% for eutrophic waters. In the future, matchups are needed for validation purposes with respect to satellite application. Moreover, new approaches that can be applied to detect subsurface chlorophyll maximum (SCM), ice-edge and/or under-ice blooms, phytoplankton functional types (PFT) and so on are expected.

Ce mémoire présente trois algorithmes qui ensemble, ont pour objectifs d’estimer la direction d’arrivée de sources sonores composées de raies spectrales non-stationnaires. Ces algorithmes permettent de faire une localisation à haute-résolution qui surpasse les performances d’un corrélateur. Le premier algorithme a comme objectifs d’estimer et de pister les composantes fréquentielles contenues dans un spectre échantillonné par un réseau linéaire uniforme. Le second utilise une version adaptée de l’algorithme MUSIC afin d’estimer la direction d’arrivée de chacune des raies spectrales pistées. Le troisième permet de focaliser les directions d’arrivée de chacune des raies spectrales vers la source qui les a émises afin de la localiser de façon précise. Finalement, ce mémoire présente des mesures expérimentales et des simulations afin de valider le fonctionnement des algorithmes.

La prédiction de séquence comporte plusieurs applications en traitement du langage naturel, en bioinformatique, et en vision numérique. La complexité de calcul requise pour trouver la séquence optimale parmi un nombre exponentiel de possibilités limite cependant l’utilisation de tels algorithmes. Dans ce mémoire, nous proposons une approche permettant de résoudre cette recherche efficacement pour deux types de problèmes différents. Plus précisément, nous adressons le problème de pré-image en prédiction de structure nécessitant de trouver la séquence associée à une entrée arbitraire, et le problème consistant à trouver la séquence qui maximise la fonction de prédiction de plusieurs classificateurs et régresseurs à noyaux. Nous démontrons que ces deux problèmes se réduisent en un même problème combinatoire valide pour plusieurs noyaux à séquences. Pour ce problème, nous proposons une borne supérieure sur la fonction de prédiction pouvant être utilisée dans un algorithme de recherche branch and bound pour l’obtention de solutions optimales. Sur les tâches de reconnaissance de mots et de prédiction de phonèmes, l’approche proposée obtient des résultats compétitifs avec les algorithmes de prédiction de structure de l’état de l’art. De plus, la solution exacte du problème de pré-image augmente de manière significative les performances de prédiction en comparaison avec une approximation trouvée par l’heuristique la plus connue. Pour les tâches consistant à trouver la séquence maximisant la fonction de prédiction de classificateurs et régresseurs, nous montrons que des méthodes existantes peuvent être biaisées à prédire de longues séquences comportant des symboles répétitifs. Nous soulignons que ce biais est enlevé lorsque le noyau est normalisé. Finalement, nous présentons des résultats en conception de médicaments sur la découverte de composés principaux. Le code source peut être téléchargé à https://github.com/a-ro/preimage. / Sequence prediction algorithms have many applications in natural language processing, bioinformatics, and computer vision. However, the computational complexity required to find the optimal sequence among an exponential number of possibilities limits the use of such algorithms. In this thesis, we propose an approach to solve this search efficiently for two types of sequence prediction problems. More precisely, we address the pre-image problem encountered in structured output prediction, which consists of finding the sequence associated with an arbitrary input, and the problem of finding a sequence maximizing the prediction function of various kernel-based classifiers and regressors. We demonstrate that these problems reduce to a common combinatorial problem valid for many sequence kernels. For this problem, we propose an upper bound on the prediction function which has low computational complexity and which can be used in a branch and bound search algorithm to obtain optimal solutions. On the practical tasks of optical word recognition and grapheme-to-phoneme prediction, the proposed approach is shown to be competitive with state-of-the-art structured prediction algorithms. Moreover, the exact solution of the pre-image problem is shown to significantly improve the prediction accuracy in comparison with an approximation found by the best known heuristic. On the task of finding a sequence maximizing the prediction function of kernelbased classifiers and regressors, we highlight that existing methods can be biased toward long sequences that contain many repeated symbols. We demonstrate that this bias is removed when using normalized kernels. Finally, we present results for the discovery of lead compounds in drug discovery. The source code can be found at https://github.com/a-ro/preimage.

L’industrie de la volaille est en pleine croissance au cours des dernières décennies. Au Québec, les producteurs de volailles sont organisés en association dans une complexe chaîne d’approvisionnement. Cette chaîne suit les principes de l’agriculture contractuelle sur un marché basé sur la gestion de l’offre. La gestion de l’offre, parmi d’autres règles, établit le prix de vente de la volaille aux épiceries. Cependant, il existe un marché spécialisé pour la volaille où le prix de vente n’est pas contrôlé par la gestion de l’offre. Ce marché spécialisé comprend le besoin de volaille fraîche de la restauration et des rôtisseries. Il est beaucoup plus profitable pour les producteurs d’approvisionner ce marché spécialisé. La coopérative partenaire de cette recherche est formée par des producteurs de volailles pour abattre et vendre leur production. La coopérative veut ajouter de la valeur à ses propriétaires en augmentant sa participation au marché spécialisé de la volaille. Cependant, ses produits ne sont pas toujours dans le standard de poids requis par ce marché. Ce mémoire présente l’étude du cas de cette coopérative, afin d’améliorer leurs processus opérationnels et d’obtenir des produits dans le poids standard établi par le marché spécialisé. On propose donc une solution à ce problème avec l’emploi de la programmation mathématique. L’algorithme de séparation et d’évaluation progressive (branch-and-bound) est appliqué pour l’obtention des résultats. On a trouvé une solution à la formulation mathématique proposée au problème opérationnel de la coopérative. Bien que la solution ait été obtenue avec un écart d’optimalité de 20%, la coopérative a vu qu’il était possible de gagner du temps dans son processus opérationnel si la solution était adoptée. La coopérative a donc décidé de transformer ce prototype en un vrai logiciel pour la planification de l’élevage. / The poultry industry faces a strong growth in the last decades. In Québec, poultry producers are organized in associations within a complex supply chain. This chain follows the principles of the contract farming in a market based on supply management. The supply management, among other rules, establishes the sales price of poultry to grocery stores. However, there is a specialized market for the poultry where the sale price is not controlled by the supply management. This specialized market gathers the need of fresh poultry for the restaurants and rotisseries. It is much more profitable for the producers to supply this specialized market. The cooperative partner of this research is composed of poultry producers to slaughter and sell their production. This cooperative wants to add value to their owners by increasing participation in the specialized poultry market. However, their products are not always within the required weight. This master thesis presents the case study of the cooperative so that they can enhance their operational processes and have the products within the standard weight established by the specialized market. We propose a solution to this problem by using mathematical programming. The branch-and-bound algorithm is used for obtaining the results. We found a solution for the mathematical formulation proposed for the operational problem. Even though the solution was obtained with an optimization gap of 20%, the cooperative noticed an opportunity to save time on the daily work in its operational process if the solution is adopted. So, the cooperative decided to transform this prototype in a real software for their production planning.

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d'ordonnancement de grande envergure. L'ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d'un ordonnancement. Résoudre un problème d'ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l'exécuter. La plupart des problèmes d'ordonnancement sont NP-Difficiles. Conséquemment, il n'existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d'ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d'explorer ces algorithmes d'ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l'arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d'ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d'optimisation n'est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d'exécuter une tâche au temps t dépend de t. / Constraint programming is a powerful methodology to solve large scale and practical scheduling problems. Resource-constrained scheduling deals with temporal allocation of a variety of tasks to a set of resources, where the tasks consume a certain amount of resource during their execution. Ordinarily, a desired objective function such as the total length of a feasible schedule, called the makespan, is optimized in scheduling problems. Solving the scheduling problem is equivalent to finding out when each task starts and which resource executes it. In general, the scheduling problems are NP-Hard. Consequently, there exists no known algorithm that can solve the problem by executing a polynomial number of instructions. Nonetheless, there exist specializations for scheduling problems that are not NP-Complete. Such problems can be solved in polynomial time using dedicated algorithms. We tackle such algorithms for scheduling problems in a variety of contexts. Filtering techniques are being developed and improved over the past years in constraint-based scheduling. The prominency of filtering algorithms lies on their power to shrink the search tree by excluding values from the domains which do not yield a feasible solution. We propose improvements and present faster filtering algorithms for classical scheduling problems. Furthermore, we establish the adaptions of filtering techniques to the case that the tasks can be delayed. We also consider distinct properties of industrial scheduling problems and solve more efficiently the scheduling problems whose optimization criteria is not necessarily the makespan. For instance, we present polynomial time algorithms for the case that the amount of available resources fluctuates over time, or when the cost of executing a task at time t is dependent on t.