identifier: Attia, D. (2020). Optimization of heterogeneous employee scheduling problems  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Le problème de planification d'horaires du personnel consiste à créer les horaires de travail des employés d'une organisation. Le nombre d'employés requis par unité de temps, appelé la demande en employés par période, est donné pour un horizon de planification. Différentes règles et contraintes régissent l'élaboration des horaires des employés. Ces règles dépendent des besoins de l'organisation, des contrats des employés et de la convention collective de travail. Le problème de planification est dit hétérogène quand il concerne des employés ayant des qualifications différentes, habituellement, dans le cadre d'un problème de planification d'employés multi-tâches ou multi-départements. Dans un contexte multi-départements avec transferts entre départements, un quart de travail peut être effectué dans son ensemble dans un département, ou un transfert de département peut avoir lieu au sein du quart de travail lorsque l'employé a les qualifications requises. Lorsque les transferts sont autorisés, le nombre de quarts de travail possibles par employé devient énorme. L'optimisation d'un tel problème est souvent essentielle pour le succès de l'organisation. Par contre, sa résolution directe comme un programme linéaire en nombres entiers s'avère impossible pour les grandes instances. Dans la première partie de cette thèse, nous proposons une heuristique de décomposition en plusieurs phases (MP-DH) pour le problème de planification des employés avec transferts. Dans ce problème, la sous-couverture et la sur-couverture sont acceptées mais pénalisés dans la fonction objectif. Un département d'origine est introduit pour chaque employé où l'employé doit travailler la majorité de son temps. En plus, il/elle peut être qualifié(e) pour travailler dans plusieurs autres départements. La première phase commence par déduire la demande en employés qui ne peut pas être couverte par les employés du département. Ces pièces de demandes extraites sont appelées intervalles critiques, car elles nécessitent des employés transférés d'autres départements pour y travailler. Cela se fait en résolvant un programme en nombres entiers de planification d'horaires de personnel anonyme pour chaque département séparément, puis en extrayant la demande non-couverte qui définit un ensemble d'intervalles critiques. Pour chacun des intervalles critiques, la deuxième phase choisit un département qui lui attribue la responsabilité de transférer un de ses employés pour travailler pendant cet intervalle critique. Ceci est accompli en résolvant un autre programme en nombres entiers de planification d'horaires de personnel anonyme avec transferts, pour un seul jour, pour chacun des jours de l'horizon. La décomposition journalière rend la taille du problème gérable spécialement pour les grandes instances. Cette phase se termine par la migration de toute demande d'un département d1 couverte par un employé d'un département d2, formant la demande de transfert d'employé de d2 vers d1. Finalement, pour chaque département, la troisième phase résout un programme en nombres entiers de planification d'horaires de personnel mono-départemental avec transfert. La demande utilisée est la nouvelle demande résultant de la migration de toutes les demandes de transfert pendant la deuxième phase. L'heuristique MP-DH a réussi à décomposer le problème de planification d'employés multidépartements en plusieurs, plus petits, problèmes de planification d'employés mono départementaux, ce qui a permis de réduire de beaucoup les temps de calcul et de transformer les grandes instances non résolubles en instances résolubles avec une légère baisse dans la qualité des solutions obtenues. Chacune des trois phases de MP-DH utilise le parallélisme. Dans la première phase, les programmes en nombres entiers des départements s'optimisent en parallèle. La deuxième phase exécute chaque problème journalier en parallèle. Enfin, la troisième phase optimise chaque département en parallèle. À la fin de chaque phase, tous les résultats des problèmes parallèles sont fusionnés pour former la solution finale. Dans les tests réalisés pour l'heuristique MP-DH, les deux premières phases sont extrêmement rapides, tandis que la troisième phase peut atteindre deux heures de temps de résolution pour les grandes instances. Pour pallier à cet inconvénient, nous présentons une heuristique hybride dans la deuxième partie de la thèse, visant à réduire fortement le temps d'exécution de la troisième phase tout en conservant la qualité de la solution. L'heuristique hybride utilise deux modèles de manière interchangeable afin de résoudre la troisième phase le plus précisément et rapidement possible. Le premier modèle est celui déjà presenté pour la troisième phase du MP-DH que nous appelons le modèle de base. Le second est un problème de planification d'horaires du personnel mono-département avec transfert semi-anonyme que nous appelons le modèle semi-anonyme. La version semi-anonyme réduit le nombre d'employés pour lesquels les horaires sont optimisés et remplace les quarts des employés restants par un ensemble de quarts anonymes agrégés, puis résout le problème pour les employés restants par la suite. L'heuristique hybride commence par résoudre le modèle de base. Si après un délai donné, l'écart d'optimalité est supérieur à un seuil donné, la résolution de modèle de base est annulé et une version semi-anonyme est résolue. Cette opération est répétée jusqu'à ce que tous les horaires des employés soient optimisés. L'heuristique hybride a réussi à réduire le temps d'exécution de la troisième phase jusqu'à 87% en moyenne, tout en perdant seulement 4 % dans le coût de la solution en moyenne. Dans la troisième partie de la thèse, nous abordons une version différente du problème de planification d'horaires de personnel, soit le problème de planification d'horaires de personnel multi-tâches, où ni les transferts ni la sous-couverture ne sont autorisés. À la place de la sous-couverture, des quarts anonymes appelés open-shifts sont utilisés pour couvrir la demande incouvrable par aucun employé. Nous développons une métaheuristique parallèle de recherche à grands voisinage (LNS) pour ce problème. Le concept de sub-scope est utilisé comme unité de décomposition dans l'algorithme LNS. Un sub-scope est défini comme: un sous-ensemble d'employés, un sous-ensemble de tâches et un sous-ensemble continu de l'horizon du problème. L'heuristique LNS est définie par des procédures de destruction et de réparation. Notre procédure de destruction choisit des sub-scopes, entraînant un coût élevé, à détruire. Lorsqu'un sub-scope d'une solution est détruit, tous les quarts travaillés pendant l'horizon du sub-scope par un employé appartenant au sub-scope, pour l'une des tâches du sub-scope, sont supprimés de la solution. Les coûts principaux affectant la fonction objectif sont les suivants: le coût de la surcouverture, le coût d'utilisation des open-shifts et la pénalité pour la violation des heures de travail minimales des employés. La procédure de destruction se concentre donc sur la destruction des sub-scopes entraînant de tels coûts dans une solution donnée. Après la destruction des sub-scopes d'une solution, la procédure de réparation reconstruit une nouvelle solution améliorée. La procédure de réparation que nous proposons résout un programme en nombres entiers de planification d'horaires de personnel multi-tâches pour les sub-scopes déjà détruits. Les procédures de destruction et de réparation sont répétées séquentiellement jusqu'à ce que la condition d'arrêt soit atteinte. La procédure de destruction parallèle détruit plusieurs sub-scopes disjoints, puis chaque subscope est réparé dans un fil (thread) parallèle différent. Nous comparons l'heuristique présentée avec le modèle exact résolu dans le système commercial WFC par Kronos Inc. Les résultats expérimentaux montrent qu'en moyenne, l'algorithme LNS parallèle peut réduire les temps d'exécution jusqu'à 80% et améliorer les coûts des solutions jusqu'à 1, 8%.  ABSTRACT: The employee scheduling problem consists of creating working schedules for an organization staff. The number of required employees per time unit, called employee requirement per period, is given for the full problem horizon. Different rules and constraints govern an employee scheduling problem, these rules depends on the organization needs, employees contracts and the collective labor agreement. A heterogeneous employee scheduling problem deals with employees having different working skills, usually within a multi-job or multi-department employee scheduling context, where one employee can be qualified for several of the organization activities, and can work for any activity he/she is qualified for. One working shift can be accomplished in a single department, or a department transfer can take place within a shift when the employee has the required skills. When a department transfer within a shift is allowed, the number of possible working shifts per employee becomes huge. Optimizing such heterogeneous employee scheduling problem is often essential for organizational success. However, solving such problems directly as a mixed integer linear program (MILP) is intractable for large instances. In the first part of this thesis, we propose a multi-phase decomposition heuristic (MP-DH) for the employee scheduling problem with inter-department transfers. In this problem, the concept of department of origin is introduced, where each employee is qualified to work in several departments, but he/she has exactly one department of origin, where the employee should work the majority of his/her time. The first phase starts by extracting from each department employee requirement, the uncoverable requirement parts by internal employees,i.e. if only the department internal employees can work. These extracted requirement parts are called critical intervals, because they need transferred employees from other departments to fulfill them. This is done by solving an anonymous employee scheduling problem modeled as a MILP for each department apart, before extracting the uncovered requirement parts that form the set of critical intervals. For each of the critical intervals, in the second phase, one department is chosen to assign it the responsibility of fulfilling this critical interval requirement, i.e. to transfer one of its employees to work during the critical interval. This is accomplished by solving a one-day anonymous employee scheduling problem with inter-department transfers for the critical intervals modeled as a MILP, for each of the problem horizon days. The day decomposition renders the problem size manageable in computer memory, especially for large instances (up to 25 departments). This phase ends by migrating any department d1 requirement covered by an employee from department d2, building a new employee transfer requirement from d2 to d1. The third phase solves, for each department, a mono-department employee scheduling problem with derived inter-department transfers as a MILP. The input to the third phase is the new final requirement resulting from the requirement migration of phase two. The MP-DH heuristic succeeds to decompose the multi-department employee scheduling problem into several mono-department employee scheduling problems to save substantial computational time. This allows to solve large instances while not deteriorating much the solution quality. Each phase of the MP-DH algorithm uses parallelism. In the first phase, all department MILPs and post-processing are accomplished in parallel. The second phase runs all singleday problems in parallel. Finally the third phase optimizes all department problems in parallel. At the end of each phase, all parallel problem solutions are merged to form the final solution. In the reported computational experiments, we observe that the first two phases are solved extremely fast compared to the third phase. The size of the solved MILPs in the first two phases is not proportional with the size of the optimized instance, while the third phase MILP size is. To overcome the computational issues of the third phase we present the hybrid heuristic in the second part of the thesis. The hybrid heuristic aims at greatly reducing the MP-DH third phase computational time, while maintaining the solution quality. The hybrid heuristic uses two models interchangeably in order to solve the third phase as accurate and as fast as possible. The first is the third phase MILP of the MP-DH algorithm, which we call the basic model. The second is a semi-anonymous employee scheduling problem with derived inter-department transfers modeled as a MILP that we call the semi-anonymous model. The semi-anonymous version reduces the number of employees for whom the schedules are optimized, and replaces the remaining employee shifts by a set of aggregated anonymous shifts. Once such a model is solved, the schedules of the selected employees are fixed and the algorithm moves on to solving another MILP where another set of employees must be scheduled. The hybrid heuristic starts by solving the basic model, then if, after a given time limit, the MILP optimality gap is higher than a given threshold, the resolution of the basic model is stopped and a semi-anonymous version is solved. This is done repeatedly until all employee schedules are optimized. The hybrid heuristic succeeded in reducing on average up to 87% of the third phase computational time while only loosing 4% in the solution quality. In the third part of the thesis, we tackle a different employee scheduling problem variant: the multi-job employee scheduling problem, where neither transfers nor under-coverage is allowed. Instead, anonymous shifts called open-shifts are used to cover any unavoidable under-coverage. The three main costs composing the objective function are: Over-coverage cost, open-shift usage cost, and minimum employees working hours violation penalty. A parallel large neighborhood search (LNS) metaheuristic for the multi-job employee scheduling problem is developed. Where a sub-scope denotes: a subset of the employees, a subset of the jobs and a continuous subset of the problem horizon. The LNS heuristic is defined by destroy and repair procedures. Our destroy procedure chooses sub-scopes coupled with a high cost in the objective function to be destroyed. When a solution sub-scope is destroyed, all shifts, occurring within the sub-scope horizon and worked by an employee belonging to the sub-scope, for one of the sub-scope jobs, are removed from the current solution schedule.Once the solution sub-scopes are destroyed, the repair operator tries to build an enhanced solution. Our proposed repair operator solves a MILP restricted to the destroyed sub-scopes. The parallel LNS destroy operator creates several disjoint sub-scopes, then each sub-scope is repaired in a different parallel thread. We compare the presented heuristic with the formal MILP solved within the commercial system WFC for Kronos Inc. Experimental results show that the parallel LNS algorithm can save up to an average of 80% in the computational time and 1.8% in the solution cost.


identifier: Benoit, N. (2020). Caractérisation stochastique des hétérogénéités hydrostratigraphiques appliquée à la modélisation hydrogéologique régionale  [Thèse de doctorat, Polytechnique Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: L'une des principales sources d'incertitude des modèles hydrogéologiques porte sur les hétérogénéités hydrostratigraphiques. Ces dernières jouent un rôle majeur sur l'écoulement de l'eau souterraine et le transport des contaminants. Pourtant la caractérisation hydrogéologique inclut très rarement l'évaluation de l'effet de l'incertitude des hétérogénéités. Cette situation s'explique en partie par la difficulté à reproduire, de manière satisfaisante, ces caractéristiques physiques en modèles équivalents. Peu ou pas de méthodologie complète et efficace permet d'effectuer la modélisation hydrogéologique régionale dans un cadre stochastique tout en quantifiant l'incertitude des hétérogénéités inter et intra unités. La difficulté de simuler efficacement les hétérogénéités inter unités de ce type de contexte est un frein à la modélisation hydrogéologique stochastique régionale. Également, la difficulté associée à la paramétrisation stochastique régionale intra unités (conductivité hydraulique ou K ) de ces modèles représente aussi un obstacle. Ces difficultés constituent une problématique majeure quand vient le besoin de quantifier adéquatement l'incertitude des modèles. Les méthodes de simulation géostatistique moderne, telles que la méthode plurigaussienne et multipoint, permettent de produire des modèles équivalents des hétérogénéités inter unités, appelés réalisations. Malgré leurs récents développements, ces méthodes conservent différentes lacunes telles que le manque de réalisme géologique dans certains contextes. Par exemple, la méthode plurigaussienne ne peut facilement incorporer des transitions asymétriques entre unités, de même que la méthode multipoint qui éprouve aussi des difficultés avec la non- stationnarité ainsi que les forts contrastes d'épaisseurs. Par contre, la méthode MCP peut s'affranchir de ces difficultés notamment grâce au transiogramme et sa propriété de forçage 0/1 des probabilités. Les hétérogénéités intra unités des modèles hydrogéologiques sont définies à partir des don- nées de K scalaire à une échelle locale. Cette échelle n'est généralement pas représentative de la taille des éléments d'un modèle hydrogéologique régional. La caractérisation stochastique de la K équivalente (tenseur-K ) à l'échelle de l'élément est un défi en soi. Elle nécessite plu- sieurs étapes incluant des contraintes à respecter dont la préservation de la structure spatiale et la contrainte d'inégalité Kverticale ≤ Khorizontale des tenseurs ainsi que les corrélations inter composantes. À cela s'ajoute, la mise à l'échelle de la K qui tient compte de l'effet des hétérogénéités locale régionalisée, la régionalisation des composantes corrélées des tenseurs-K des différentes unités ainsi que leur calage avec les variables d'état (p. ex. charge hydraulique) dans un contexte multivariable contraint. Une méthodologie complète devrait également fournir des réalisations significativement différentes afin de quantifier adéquatement l'incertitude associée aux tenseurs-K. L'objectif général de la thèse consiste à développer une démarche complète de caractérisation stochastique de l'incertitude des hétérogénéités inter et intra unités hydrostratigraphiques appliquées à la modélisation hydrogéologique régionale. Plus spécifiquement, la thèse vise à développer une méthodologie de simulation géostatistique des unités hydrostratigraphiques (UHS) afin de fournir des modèles équivalents d'aspect réaliste pour un contexte de sédimentation directionnelle (asymétrie) et à développer une méthodologie de caractérisation stochastique, de mise à l'échelle et de calage des tenseurs-K équivalents à partir de la K scalaire tout en préservant la structure spatiale des tenseurs, la contrainte d'inégalité ainsi que les corrélations inter composantes. La méthodologie globale s'oriente autour de trois étapes principales : i) la compilation et la préparation des données, ii) la simulation de modèles hydrostratigraphiques directionnels et iii) la caractérisation stochastique des tenseurs-K. La première étape a porté sur la compilation et le traitement des données (hydrostratigraphie et K) pour les développements méthodologiques et les différents tests méthodologiques appliqués sur le sous-bassin Innisfil Creek (comté de Simcoe, Ontario). La deuxième étape est basée sur le développement d'une démarche de simulation par la méthode MCP afin de générer des modèles équivalents dans un contexte hydrostratigraphique 3D complexe dont la séquence des unités est ordonnée verticalement. La méthodologie proposée inclut l'estimation des probabilités bivariables par transformée de Fourier à partir du modèle déterministe et des critères de qualité de simulation. La méthode est testée pour montrer sa capacité à quantifier la variabilité locale de la solution et son incertitude. La troisième étape fournit une méthodologie complète de caractérisation stochastique des hétérogénéités intra UHS qui inclut : la mise à l'échelle d'hétérogénéités locales (K) en tenseur-K équivalent, l'utilisation du modèle linéaire de corégionalisation pour la simulation des composantes des tenseurs-K équiprobables, la préservation des corrélations entre les composantes des tenseurs-K par nouvelle transformation gaussienne bivariée et l'utilisation de la méthode de déformation graduelle (GDM) pour caler les tenseurs-K en fonction des observations de charge hydraulique. Les résultats montrent la capacité de la méthode MCP à simuler efficacement un contexte hydrostratigraphique régional 3D complexe avec de multiples unités. De plus, les résultats montrent la capacité de la méthode à reproduire l'ordination verticale des unités et tout ça malgré la forte hypothèse d'indépendance conditionnelle. Les résultats des simulations conditionnelles et non conditionnelles pour le cas synthétique montrent clairement l'absence de tout biais substantiel. Dans l'exemple plus complexe du contexte réel, le biais est moins important pour le cas non conditionnel et pour l'échantillonnage aléatoire des données que pour le biais observé dans les données dû à l'échantillonnage préférentiel. La surreprésentation de données conditionnantes n'a pas d'impact significatif sur les proportions moyennes simulées mais l'ajout de données supplémentaires réduit la variabilité. Soulignons que la méthode MCP fournit de bons résultats malgré une image d'entraînement fortement non stationnaire. Avec une autre méthode (PGS ou MPS), rien n'aurait garanti un tel succès dans le contexte étudié. Les résultats de la méthodologie de caractérisation de la K montrent que la nouvelle méthode proposée fournit des modèles équivalents calés des tenseurs-K. La méthode de mise à l'échelle de la K scalaire en tenseur-K équivalent tient compte de la structure des hétérogénéités locales et des propriétés statistiques de chacune des UHS. La régionalisation des composantes des tenseurs-K effectuée par simulation géostatistique à partir de modèles linéaires de corégionalisation (LCM) rend le temps de calcul raisonnable. La simulation reproduit aussi, pour chacune des unités, les caractéristiques statistiques des différentes composantes de K. Pour rétablir les corrélations non linéaires des tenseurs-K non-gaussiens ainsi que les histogrammes des composantes souhaités, une nouvelle transformation bivariée est appliquée sur les réalisations. Les résultats du calage des tenseurs-K montrent que la méthode des déformations graduelles permet le calage multivariable contraint tout en préservant la covariance spatiale et croisée de UHS. Il a été démontré que la méthode conserve les relations non linéaires entre les composantes du tenseur-K grâce à l'intégration de la transformation bivariée. L'approche proposée a ainsi permis de préserver les propriétés spatiales des tenseurs ainsi que les relations entre les composantes. Les résultats démontrent que la GDM s'applique à un contexte multivariable contraint et pas seulement au contexte univariable. Soulignons que les inversions convergent rapidement en termes du nombre d'itérations grâce à l'optimisation du paramètre de déformation de la GDM. Il a aussi été montré que la méthode permet de caler la recharge séparément ou simultanément avec les tenseurs-K. Les exemples de calage montrent qu'il est avantageux d'inclure la recharge stochastique dans l'inversion. Par ailleurs, il a été observé qu'un nombre élevé d'observations de charge n'améliore pas significativement les résultats. Une comparaison, portant sur la définition de zones de captage autour de deux puits de pompage, entre la méthode GDM proposée et la méthode d'inversion PEST montrent des tenseurs-K géologiquement plus réalistes avec GDM que ceux obtenus avec PEST. L'ensemble des résultats permet de conclure que la méthode MCP simule efficacement un contexte régional complexe d'une succession stratigraphique directionnelle d'un bassin sédimentaire glaciaire. La méthode prend efficacement en charge la forte non-stationnarité spatiale des unités ainsi que d'imposantes contraintes comme la déposition verticale ordonnée en tenant compte de l'asymétrie stratigraphique à partir des probabilités de transition entre les unités. La méthode MCP s'est révélée sans biais dans le cas non conditionnel. La méthodologie proposée de caractérisation des tenseurs-K permet le calage individuel ou simultané des tenseurs-K de différentes UHS et/ou de recharge. La méthodologie inclut une mise à l'échelle des conductivités hydrauliques quasi ponctuelles vers un tenseur équivalent en tenant compte de la structure spatiale à l'échelle locale. Bien que la mise à l'échelle soit intensive en temps de calcul, il a été démontré qu'il est possible de limiter au minimum le nombre d'éléments à mettre à l'échelle grâce à la régionalisation des tenseurs-K par simulation géostatistique. La thèse a apporté quelques contributions originales. D'abord, il s'agit d'une première appli- cation de la méthode MCP pour la simulation 3D. À ma connaissance, aucune autre méthode de simulation stochastique ne semble être en mesure de solutionner avec autant de satisfaction un contexte hydrostratigraphique complexe 3D comme celui du comté de Simcoe. La méthode des déformations graduelles permet le calage efficace des composantes des tenseurs- K avec préservation des corrélations non linéaires des composantes et de leurs fonctions de covariance. À ma connaissance, il s'agit de la première approche utilisant la GDM pour un contexte multivariable avec contraintes. Enfin, cette thèse contribue à l'avancement des connaissances et des techniques de la caractérisation stochastique des hétérogénéités inter et intra hydrostratigraphiques. Dans une plus grande perspective, la thèse contribue à fournir des outils adaptés pour mieux quantifier l'incertitude associée aux hétérogénéités présente dans les modèles hydrogéologiques régionaux.  ABSTRACT: One of the main sources of uncertainty in hydrogeological models relates to hydrostrati- graphic heterogeneities. They play a major role in quantification of groundwater dynamics and mass transport. Yet hydrogeological characterization rarely includes the assessment of the effect of uncertainty and spatial variability of hydrostratigraphic units and hydrogeologic parameters. This is partly explained by the difficulty of reproducing these physical charac- teristics satisfactorily in equivalent models. There is at present little or no comprehensive and efficient methodology that allows regional hydrogeological modelling to be carried out in a stochastic framework while quantifying the uncertainty of inter- and intra-unit hetero- geneities. The difficulty to effectively simulate inter-unit heterogeneities under such condi- tions is a hindrance to stochastic regional hydrogeological modelling. As well, the difficulty associated with the regional stochastic intra-unit parameterization (hydraulic conductivity or K ) of these models further aggravates the problem. These difficulties constitute a major issue when it comes to the need to adequately quantify model uncertainty. Modern geostatistical simulation methods, such as plurigaussian and multipoint simulations, make it possible to produce equivalent models of inter-unit heterogeneities, referred to as realizations. Despite their recent developments, these methods retain various shortcomings such as the lack of geological rigour in certain settings. For example, the plurigaussian method cannot easily incorporate asymmetrical transitions between units, whereas the multipoint method has dif- ficulties with non-stationarity and strong thickness contrasts. On the other hand, the MCP (Markov-type categorical prediction) method has the capacity to overcome these difficulties thanks to the transiogram and its 0/1 probability forcing property. The intra-unit heterogeneities of the hydrogeological models are defined from scalar K data at a local scale. This scale is generally not representative of the size of the elements used in regional hydrogeological models. Stochastic characterization of the equivalent K (K -tensor) at the element scale is a challenge in itself. It requires several steps including constraints to be respected such as the preservation of the spatial structure, the natural constraint Kvertical ≤ Khorizontal, and the inter-component correlations. In addition, the upscaling of K takes into account the effect of local heterogeneities, the regionalization of the correlated components of the K -tensors of the different units and their calibration with state variables (e.g., hydraulic head) in a constrained multivariate context. A comprehensive methodology should also provide significantly different realizations in order to adequately quantify the uncertainty associated with the K -tensors. The general objective of this thesis is to develop a comprehensive approach to stochastic characterization of the uncertainty of inter- and intra-hydrostratigraphic unit heterogeneities applied to regional hydrogeological modelling. More specifically, the thesis aims to develop a methodology for geostatistical simulation of hydrostratigraphic units (HSU) in order to provide equivalent models of realistic appearance for a directional sedimentation context (asymmetry) and to develop a methodology for stochastic characterization, upscaling and calibration of equivalent K -tensors from the scalar K while preserving the spatial structure of the tensors, the inequality constraint as well as the inter-component correlations. The overall approach revolves around three main steps: (i) data compilation and preparation, (ii) simulation of directional hydrostratigraphic models, and (iii) stochastic characterization of K -tensors. The first step focuses on data compilation and processing (hydrostratigraphy and K ) for methodological developments and various methodological tests applied to the Innisfil Creek sub-watershed (Simcoe County, Ontario). The second stage is based on the development of a simulation approach using the MCP method to generate equivalent models in a complex 3D hydrostratigraphic context with a vertically ordered sequence of units. The proposed methodology includes the estimation of bivariate probabilities by Fourier transform from the deterministic model and the simulation quality criteria. The method is tested to show its ability to quantify the local variability of the solution and its uncertainty. The third step provides a complete methodology for stochastic characterization of intra-HSU heterogeneities which includes: upscaling of local heterogeneities (K ) into equivalent K - tensors, use of the linear co-regionalization model for simulation of equiprobable K -tensor components, preservation of correlations between K -tensor components by new bivariate Gaussian transformation and use of the Gradual Deformation Method (GDM) to calibrate the K -tensors according to hydraulic head observations. The results show the ability of the MCP method to effectively simulate a complex 3D regional hydrostratigraphic with multiple units. Furthermore, the results show the ability of the method to reproduce the vertical ordering of the units, despite the strong assumption of conditional independence. The results of the conditional and unconditional simulations for the synthetic case clearly show the absence of any substantial bias. In the more complex example of field hydrogeological settings, the bias is less important in the unconditional case and in the random sampling case than the bias observed in the data due to preferential sampling. Over-representation of conditioned data does not have a significant impact on the mean simulated proportions, but the addition of supplementary data reduces variability. The MCP method provides good results despite a highly non-stationary training image. With another method (PGS or MPS), nothing would have guaranteed such success in the studied context. The results of the K characterization methodology show that the presented original method provides equivalent calibrated models of the K -tensors. The scalar K upscaling method to equivalent K -tensor takes into account the structure of local heterogeneities and the sta- tistical properties of each of the HSU. The regionalization of the K -tensor components by geostatistical simulation using Linear Co-Regionalization Models (LCMs) keeps the compu- tation time reasonable. The simulation also reproduces, for each of the units, the statistical characteristics of the different K components. To restore the non-linear correlations of the non-Gaussian K -tensors as well as the histograms of the desired components, a new bivariate transformation is applied to the realizations. The results of the calibration of the K -tensors show that the method of gradual deformations allows the multivariate constrained calibration while preserving the spatial and cross-covariance of HSU. The method has been shown to preserve the non-linear relationships between the K -tensor components through the integra- tion of the bivariate transformation. The proposed approach has thus preserved the spatial properties of the tensors and the relationships between the components. The results show that the GDM applies to a constrained multivariate context and not only to the univariate context. It should be noted that the inversions converge rapidly in terms of the number of iterations thanks to the optimization of the deformation parameter of the GDM. It has also been shown that the method allows to set the recharge separately or simultaneously with the K -tensors. The calibration examples show that it is advantageous to include stochastic recharge in the inversion. It has also been observed that a high number of head observations does not significantly improve the results. A comparison of the definition of capture zones around two pumping wells between the proposed GDM method and the PEST inversion method shows geologically more realistic K -tensors with GDM than those obtained with PEST. The overall results suggest that the LCM method effectively simulates a complex regional context of a directional stratigraphic succession in a glacial sedimentary basin. The method effectively supports the strong spatial non-stationarity of the units as well as imposing con- straints such as ordered vertical deposition by taking into account stratigraphic asymmetry from the transition probabilities between the units. The MCP method proved to be unbiased in the unconditional case. The proposed K -tensor characterization methodology allows in- dividual or simultaneous calibration of K -tensors from different HSU and/or recharge units. The methodology includes an upscaling of quasi-point hydraulic conductivities to an equiva- lent tensor taking into account the spatial structure at the local scale. Although the upscaling is computationally intensive, it has been shown that it is possible to minimize the number of elements to be scaled by regionalizing the K -tensors by geostatistical simulation. The thesis provided substantial original contributions. This is a first application of the MCP method for 3D simulations. To the author's knowledge, no other stochastic simulation method seems to be able to solve as satisfactorily a 3D hydrostratigraphic context as complex as that of Simcoe County. The gradual deformation method allows for efficient calibration of the K - tensor components while preserving the non-linear correlations of the components and their covariance functions. To the author's knowledge, this is also the first time where GDM has been used in a multivariate context with constraints. Finally, this thesis contributes to the advancement of knowledge and techniques for stochastic characterization of inter- and intra- hydrostratigraphic heterogeneities. In a broader perspective, the thesis contributes original methods and tools adapted to better quantify the uncertainty associated with heterogeneities present in regional hydrogeological models.


identifier: Belot, I. B. (2020). Étude numérique de l'impact de la distribution de catalyseur sur les performances des filtres à particules catalytiques  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Les moteurs essence à injection directe (EID) sont une technologie en vogue pour limiter les émissions de gaz à effet de serre, grâce à d'importantes économies de carburant comparé aux autres technologies d'essence. Cependant, d'autres polluants sont émis par les véhicules à combustion interne, comme les particules fines et les oxydes d'azote (NOX) par exemple. Pour les traiter, des filtres à particules (FAP) et des chambres catalytiques (CC) sont appliqués aux systèmes de traitement des gaz d'échappement par les manufacturiers. Ces deux dispositifs sont constitués de monolithes fait de canaux rectangulaires. Dans le cas du FAP, les murs des canaux sont composés d'une céramique poreuse qui filtre les aérosols. Dans le cas des CC, les canaux sont imperméables à l'écoulement des gaz d'échappement et recouverts de catalyseur dans lequel les espèces chimiques à traiter diffusent. Afin d'abaisser les coûts et le volume de ces deux systèmes, il est possible d'intégrer le catalyseur directement dans la céramique qui forme les canaux du FAP. On parle alors de filtre à particule catalytique (FAPC). Cependant, cette déposition altère de façon significative les caractéristiques géométriques du FAPC à l'échelle du mur poreux. De plus en plus d'études s'intéressent ainsi à évaluer l'impact du dépôt de catalyseur sur les performances du FAPC en fonction, par exemple, de la quantité introduite, de la différence entre une déposition dans le mur ou sur le mur, ou encore d'un recouvrement par zones le long de chaque canal.  ABSTRACT: Particulate filters (PF) have been used very successfully during the past decade to reduce particulate matter from the exhaust gas of modern vehicles. They consist in honeycomb monoliths made out of rectangular channels in most cases. These channels are alternatively plugged at the inlet or the outlet in order to force the exhaust gases to go through the porous material composing its walls. Catalytic chambers (CC) are open monoliths coated with precious metal composed catalysts. By diffusing in the catalyst, noxious gases as carbon monoxide (CO), nitrogen oxides (NOX) and hydrocarbons (HC) are reduced or oxidized in armless components like CO2, H2O and N2.


identifier: Pont, M. (2020). Excitation résonante d'un centre isoélectronique de Te dans le ZnSe  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Les technologies NISQ (noisy intermediate-scale quantum, ou quantiques d'échelle intermédiaire bruitées), précurseurs des ordinateurs quantiques, ont déjà réussi pour certaines procédures spécifiques à dépasser les capacités de calculs d'un ordinateur classique. Le développement d'un ordinateur capable d'implémenter n'importe quel algorithme quantique reste cependant un problème ouvert. Le développement d'un système capable de stocker, de manipuler et de retranscrire l'information quantique est à l'étude dans les laboratoires du monde entier. Le réseau permettant de relier entre eux des ordinateurs quantiques à grande distance pourrait utiliser le photon comme support de l'information quantique. Les interfaces capables de faire le lien entre un qubit stationnaire, c'est-à-dire l'information quantique au sein de l'ordinateur, et un photon doivent allier un fort couplage avec la lumière à un faible élargissement inhomogène. La molécule de Te2 dans le ZnSe est un centre isoélectronique. Ces émetteurs quantiques jusqu'à maintenant peu étudiés allient le faible élargissement inhomogène des défauts atomiques comme les centres NV dans le diamant, au fort moment dipolaire des structures nanoscopiques comme les boites quantiques. On a démontré que l'initialisation d'un trou lié à une molécule de Te2 dans le ZnSe est réalisée en 150 ps avec une fidélité de 98.5%. Dans ce mémoire on fait état d'un obstacle dans la démonstration du contrôle cohérent d'un exciton lié à une molécule de Te2 dans le ZnSe. L'excitation résonante de l'exciton lié, pourtant indispensable au contrôle complet de l'état quantique de ce système à deux niveaux, engendre une accumulation de charges isolées dans le voisinage de l'émetteur. Les fluctuations de l'environnement électrostatique de l'exciton entrainent un décalage spectral variable, sous forme de diffusion spectrale, de son énergie de résonance et réduisent fortement le temps de cohérence de l'exciton. Cette observation expérimentale n'a encore jamais était reportée pour un émetteur unique. Pour contourner ce problème, on propose une solution innovante. On démontre que l'ajout d'un laser non-résonant permet de générer des paires électron-trou qui déchargent l'environnement en permettant la recombinaison radiative des charges isolées. On retrouve alors l'énergie de résonance de l'émetteur et une largeur spectrale comparable à celle attendue dans la limite radiative.  ABSTRACT: NISQ (noisy intermediate-scale quantum) technologies are the precursors of quantum computers. They have already succeeded in exceeding the computational capacity of a classical computer. However, the development of a computer that could implement any quantum algorithm remains an open problem. The development of a system capable of storing, manipulating and transcribing quantum information is under study in laboratories around the world. In order to interconnect far away computers, we could use the photon as a medium for quantum information. Interfaces capable of making the link between a stationary qubit and a photon must combine a strong coupling with light with a weak inhomogeneous broadening. The Te2 molecule in ZnSe is an isoelectronic center. These quantum emitters combine the weak inhomogeneous widening of atomic defects like NV centers in diamonds, and the high dipole moment of nanoscopic structures like quantum dots. We have shown that the initialization of a hole linked to a molecule of Te2 in ZnSe is carried out in 150 ps with a fidelity of 98.5%. In this master thesis, we first point out an obstacle in the demonstration of the coherent control of an exciton bound to a Te2 molecule in ZnSe. The resonant excitation of the bound exciton, however essential for the complete coherent control of the quantum state of this two-level system, generates an accumulation of isolated charges in the vicinity of the emitter. Fluctuations in the electrostatic environment of the exciton cause a sporadic red-shift of its resonance energy. In addition, these fluctuations greatly reduce the coherence time of the exciton. To circumvent this problem, we show that an additional non-resonant laser, that generates electron-hole pairs, discharges the environment by allowing for the radiative recombination of the isolated charges. The resonance energy of the emitter is restaured and we measure a spectral width comparable to that expected in the radiative limit.


identifier: Thomasset, C. (2020). SERENIoT : politiques de sécurité collaboratives pour maisons connectées  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Le domaine de la maison connectée est en plein essor. L'internet des objets (IoT) apporte de nouveaux services dans l'habitat pour répondre aux évolutions énergétiques, numériques et de bien-être. Cependant ces objets connectés peuvent créer des failles de sécurité dans les environnements domestiques mettant en péril la sécurité des utilisateurs et des réseaux. Le contexte de l'environnement domestique impose un prix des équipements faible, une diversité de dispositifs très importante et des solutions de sécurité ne nécessitant pas d'action de l'utilisateur. L'ensemble de ces facteurs complique la mise en oeuvre de solutions de sécurité performantes et adaptées aux réseaux IoT domestiques. La recherche menée porte sur le développement d'un système permettant une gestion autonome des politiques de sécurité pour sécuriser les installations IoT domestiques. Elle montre que les politiques de sécurité à appliquer pour sécuriser les dispositifs IoT domestiques peuvent être générées en observant leurs comportements au sein de différentes installations. L'objectif s'articule autour de la conception d'un système permettant la création et la mise en application de politiques de sécurité grâce à un système de filtrage réseau au niveau IP.  ABSTRACT: The recent development of the Internet of Things (IoT) brings new services to homes to improve energy efficiency and users' well-being. However, these new smart devices can create security holes in home environments, placing the security of users and networks at risk. The design and deployment of effective security solutions tailored to home IoT networks is made difficult by the wide diversity of devices along with the constraints of equipment costs and impact on usability. This thesis focuses on the development of a system allowing autonomous management of security policies to secure home IoT installations. The system demonstrates that the security policies for consumer IoT devices can be generated by observing their behavior within different installations. The goal was to design an autonomous system capable of generating and enforcing security policies by monitoring the network at IP level.


identifier: Khraimeche, Y. (2020). Adaptation de domaine non supervisée pour la ré-identification de personnes dans des vidéos  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: La ré-identification de personnes (ReID) vise à faire correspondre les identités de personnes à travers un réseau de caméras de vidéosurveillance. Cette tâche de reconnaissance précise est un élément clé de plusieurs tâches d'analyse vidéo dans les réseaux de caméras connectées à grande échelle dans les villes intelligentes, telles que le suivi multi-objets multi-caméras ou la recherche de personnes. C'est une tâche difficile en raison de la grande variation intra-classe causée par plusieurs facteurs, par exemple la pose, le point de vue, l'arrière-plan, l'éclairage, les occlusions, l'étalonnage de la caméra, etc. Malgré ces difficultés, les modèles d'apprentissage profonds ont récemment considérablement amélioré les performances des méthodes de ReID de personnes, dépassant même la précision humaine. Un réseau de ReID apprend à générer des caractéristiques discriminantes encapsulant l'identité d'une personne tout en étant indépendant des facteurs de variation intra-classe. Cependant, cette affirmation n'est vraie que dans un cadre supervisé dans lequel nous avons accès à un ensemble d'entraînement d'images annotées du domaine. Les caractéristiques de ReID ne se généralisent pas bien. Lorsque les réseaux sont appliqués à un domaine différent de celui sur lequel ils ont été entraînés, les performances des modèles ReID s'effondrent car les vecteurs de caractéristiques en sortie ne sont pas adaptés à ce nouveau domaine. Les images du nouveau domaine peuvent être très différentes des images d'entraînement en raison de l'environnement, de l'éclairage, du point de vue, des paramètres et du modèle de caméra différents, etc. Toutes ces variations viennent s'ajouter aux variations intra-classe, et le réseau de ReID échoue car il n'est pas entraîné pour y faire face.  ABSTRACT: Person re-identification (ReID) aims at matching pedestrian identities across a non-overlapping video surveillance camera network. This fine-grained recognition task is a key component for several video analysis tasks in connected large-scale camera network in smart cities, such as multi-target multi-camera tracking or person retrieval. It is a challenging task due to the large intra-class variation caused by multiple factors, for example pose, viewpoint, background, lighting, occlusions, camera calibration, etc. Despite these difficulties, deep learning models have recently improved significantly the performance of person ReID methods, even surpassing human accuracy. A ReID network learns to generate discriminative features encapsulating the identity of a person while being independent to the intra-class variations factors. However, this statement is only true in a supervised setting in which we have access to a training set of domain-related labelled images. ReID features do not generalize well. When the networks are applied to a domain different from the one they were trained on, the performance of ReID models collapses since the output feature vectors are not adapted to this new domain. Images from the new domain can be widely different from the training images because of different environment, lighting, viewpoint, camera settings and model, and so on. All added variations are factoring with the intra-class ones, and the ReID network fails since it is not trained to deal with these.


identifier: Sein Minn, S. M. (2020). The Analysis of Student Traces for Q-Matrix Refinement and Knowledge Tracing  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Nous assistons à une effervescense de l'auto-apprentissage rendue possible par l'Internet et les environnements d'apprentissage. L'accessibilité des MOOCS et des environnements d'apprentissage informatisés en est une manifestation. En contrepartie, l'apprenant perd le guidage personnalisé d'un tuteur humain et le développement d'environnements d'apprentissage adaptatifs vise à combler cette lacune. Afin d'offrir guidage et personnalisation au long du processus d'apprentissage, il est essentiel de bien évaluer les connaissances acquises de l'apprenant et d'adapter le matériel didactique en conséquence. Les recherches dans les domaines des tutoriels intelligents et de l'analytique des données éducationnelles visent essentiellement à développer des modèles de connaissances pouvant offrir le support à la personnalisation de l'apprentissage. Je propose dans cette thèse de nouvelles approches à la modélisation des connaissances apprenants autour de deux axes. Le premier porte sur l'objectif de valider les connaissances et compétences sous-jacentes à des tâches à partir de données. La classification de questions et exercices en une taxonomie d'objectifs d'apprentissage est un exemple pratique d'identification de compétences sousjacentes que les enseignants et pédagogues font couramment. Les chercheurs du domaine de la modélisation cognitive (Cognitive Diagnostic Modeling) vont plus loin en identifiant plusieurs connaissances et compétences derrière un seul problème à résoudre par exemple. Cet exercice est intrinsèquemet difficile et sujet aux erreurs. Les recherches pour faciliter la validation des connaissances sous-jacentes sont connues sous le nom du raffinement d'une Q-matrice qui représente l'alignement des tâches aux connaissances requises. La dernière décennie a été témoin de développements importants autour des approches basées sur les données pour effectuer le raffinement de Q-matrices. Ce processus de raffinement peut être considéré comme un problème de classification : pour chaque alignement tâche-connaissance défini par l'expert, l'algorithme de classification doit décider s'il est correct ou incorrect. Alors que la majorité des algorithmes portent sur une décision par alignement individuel, nous proposons une approche de classification basée sur des algorithme multi-classe où l'ensemble des connaissances requises par une tâche est soumises, plutôt que chaque connaissance individuellement. Les résultats de l'approche démontrent que le raffinement est généralement de meilleur qualité que les techniques de l'état de l'art. Le second axe vise à améliorer les modèles d'apprentissage profond pour l'évaluation des connaissances de l'apprenant à partir de traces séquentielles du succès ou échecs aux tâches. Nous tablons sur un modèle d'évaluation de connaissances capable de capturer l'évolution temporelle du profil de connaissance qui évolue au long du processus d'apprentissage de l'apprenant. Les algorithmes d'apprentissage profond utilisant une architecture LSTM (Long Short-Term Memory) aspirent à cet objectif de mémoriser les informations temporelles et réussissent effectivement à mieux prédire les performances des apprenants. Mais le profil de connaissance constitue un mécanisme plus explicite de l'état de connaissance atteint et plus efficace pour synthétiser cet état. Nous intégrons donc ce mécanisme à une architecture LSTM et à une architecture de réseau de mémoires (memory networks) afin de valider cette hypothèse. Le profil de connaissance est modélisé sous forme de classes et cette information est encodée par un vecteur binaire de longueur unitaire (one-hot) qui est fourni en entrée aux modèles d'apprentissage profond.  ABSTRACT: The growth of self-learning, enabled by the availability on the Internet of different forms of didactic material such as MOOCs and tutoring systems, increases in turn the relevance of personalized instructions for students in adaptive learning environment. For providing adaptive and personalized learning instructions, the assessment of student's mastery of a topic and the estimation of when she actually knows how to answer problems correctly is recognized as paramount in the fields of learning analytics and educational data mining community. In this dissertation, I propose novel approaches for building skills and student learning models along two axes. The first axis is to recover and ensure the quality of skills sets behind problems in learning system. The second axis is on improving the predictive accuracy of students' performance based on student ability profile on skills and considering of difficulty of the problem dynamically. Both of these axes are complementary and essential in knowledge assessment of future educational learning systems for equipping intelligent agents to provide adaptive instructions and independent learning environment for students. The first axis is referred to as the Q-matrix refinement problem and consists in validating an expert-defined mapping of exercises and tasks to underlying skills. The last decade has witnessed a wealth of data driven approaches aiming to refine expert-defined mappings. This refinement can be seen as a classification problem: for each possible mapping of task to skill, the classifier has to decide whether the expert's advice is correct, or incorrect. Whereas most algorithms are working at the level of individual mappings, we introduce an approach based on a multi-label classification algorithm that is trained on the mapping of a task to all skills simultaneously. This approach improves Q-matrix validation methods by using supervised multi-label classifier. Results show it outperforms the existing Q-matrix refinement techniques. The second axis aims to improve deep learning models of skills assessment based on sequential data. The student skills model needs to capture the temporal nature of student knowledge, changing over time, based on the learning transferred from previous practice. Deep learning has achieved a large amount of success in student performance prediction with models relying on Long short-term memory (LSTM). We proposed two approaches called Deep Knowledge Tracing and Dynamic Student Classification (DKT-DSC) and Dynamic Student Classification on Memory Networks (DSCMN) based on LSTM and key-value memory networks. We apply k-means clustering to capture students' temporal ability profile at each time interval, which serves as a transfer learning mechanism across student's long-term learning process. DKT DSC can capture temporal ability profile, utilize ability profile in assessment of knowledge mastery state simultaneously. The second approach, DSCMN, utilizes problem difficulty in prediction of student performance. According to experimental results, these approaches show improvements in student performance prediction over other state-of-the-art methods (such as BKT, PFA, etc.).


identifier: Fortin-Deschênes, M. (2020). Real-Time and Atomic-Level Studies of the Growth, Phase Transformations and Stability of Two-Dimensional Pnictogens  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Les pnictogènes, ou éléments du groupe VA sont composés de l'azote (N), du phosphore (P), de l'arsenic (As), de l'antimoine (Sb) et du bismuth (Bi). Grâce à leur configuration électronique de valence (ns2 np3), ils adoptent une hybridation sp3 et forment trois liens covalents en phase solide. Dû à cette configuration électronique unique, les pnictogènes, avec le graphite, sont les seuls matériaux élémentaires à se cristalliser en structures en couches van der Waals (vdW) et quasi-vdW. Typiquement, les éléments légers du groupe VA forment des solides de la phase orthorhombique A17 tandis que les éléments lourds préfèrent la phase rhomboédrique A7. Avec leur structure en couches, les pnictogènes sont des candidats idéaux pour former des matériaux bidimensionnels (2D). En effet, des couches 2D de phosphore noir (A17) ont été obtenues par exfoliation de cristaux massifs en 2014. Le 2D-P a été identifié comme étant un semiconducteur à mobilité élevée ayant des propriétés de transport anisotropes et possédant une bande interdite directe dont l'amplitude augmente graduellement de 0.3 à 2 eV en passant du matériau massif à des couches d'épaisseur atomique. Toutefois, au début de ce projet, la plupart des pnictogènes 2D n'existaient que sous forme de prédictions théoriques. En effet, on prédisait que les matériaux 2D légers du groupe VA seraient des semiconducteurs à large bande interdite, tandis que les pnictogènes lourds subiraient plusieurs transitions de phase électronique et topologique lorsqu'ils approcheraient des épaisseurs atomiques.  Cette thèse vise à développer la synthèse de nouveaux pnictogènes 2D et à élucider les mécanismes gouvernant leur croissance, leur stabilité thermodynamique, ainsi que leurs propriétés physiques de base. La croissance par épitaxie par jets moléculaires (MBE) sur des substrats semiconducteurs et vdW, les transitions de phase et la décomposition thermique de matériaux 2D du groupe VA a été étudiée en temps réels par microscopie électronique à faible énergie (LEEM). De plus, leurs propriétés structurelles, électroniques et thermodynamiques ont été élucidées par la combinaison de calculs ab initio avec des mesures de diffraction d'électrons lents (LEED), de microscopie par effet tunnel (STM), de microscopie électronique en transmission à balayage (STEM) et de microscopie de photoélectrons par rayons-X (XPEEM).  ABSTRACT: Pnictogens, also known as group VA elements, are comprised of nitrogen (N), phosphorus (P), arsenic (As), antimony (Sb) and bismuth (Bi). With their ns2 np3 valence electronic configuration, pnictogens tend to adopt a sp3 hybridization and form three covalent bonds in elemental solids. This unique electronic configuration makes them the only elemental materials, alongside graphite, to crystallize in van der Waals (vdW) and quasi-vdW layered structures. Light group VA elements tend to assemble in the orthorhombic phase (A17) and heavier group VA elements prefer the rhombohedral phase (A7). With their layered structures, pnictogens are ideal candidates to form two-dimensional (2D) materials. In fact, 2D black phosphorus (A17) has been exfoliated from bulk crystals in 2014 and was identified as a high mobility 2D semiconductor with a thickness-dependent direct band gap varying between 0.3-2 eV and displaying interesting anisotropic transport properties. However, by the time this project was initiated, most 2D pnictogens existed only in the realm of theoretical predictions. In fact, it was hypothesized that light group VA 2D materials would be large band gap semiconductors, whereas heavy 2D pnictogens were predicted to exhibit several electronic and topological transitions at near atomic thicknesses.  This thesis aims at developing growth methods for novel 2D pnictogens allotropes and at establishing an atomic-level understanding of the mechanisms governing their growth, thermodynamic stability and basic physical properties. The molecular beam epitaxy (MBE) growth on semiconducting and vdW substrates, the phase transformations and the thermal decomposition of group VA 2D materials was studied in real-time using low-energy electron microscopy (LEEM). Furthermore, their structural, electronic and thermodynamic properties were elucidated by a combination of ab initio calculations, low-energy electron diffraction (LEED), scanning tunnelling microscopy (STM), scanning transmission electron microscopy (STEM) and synchrotron-based X-ray photoemission microscopy (XPEEM).


identifier: Natsui, M. (2020). Lightning Induced Overvoltages Caused by Non-Vertical Lightning and Earth Current Behavior  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Les surtensions induites par la foudre deviennent un sujet important dans le domaine des réseaux de distribution. Une évaluation précise des tensions induites est très essentielle pour la protection contre la foudre. Un problème des évaluations existantes est qu'un canal de foudre vertical et une terre parfaitement conductrice, qui ne sont pas réalistes, sont supposés dans la plupart des cas. Ces hypothèses nécessitent des recherches plus approfondies pour une évaluation précise de la tension induite. L'objectif principal de cette thèse est de révéler et résumer (1) les influences de la foudre non verticale sur les surtensions induites par la foudre dans les réseaux de distribution et (2) le comportement du courant de foudre dans une terre avec pertes, pour une évaluation précise des tensions induites. Pour (1), les circuits du modèle FDTD pour représenter la foudre non verticale sont construits et les influences de la foudre non verticale sur les tensions induites sont étudiées avec diverses conditions telles que la forme d'onde du courant de foudre, la géométrie du canal de foudre, l'état de la terre et la distribution ligne, etc. De plus, le mécanisme des changements est discuté en comparaison avec une formule analytique. Il est clair que l'inclinaison de la foudre vers la ligne augmente considérablement les tensions induites. Les tensions atteignent plus de deux fois plus que celles du boîtier vertical. L'inclinaison le long de la ligne ne montre que des différences mineures sur la tension de crête alors qu'elle rend le profil de tension le long de la ligne asymétrique. Des tendances similaires sont observées même lorsque l'on suppose une ligne triphasée réaliste avec mises à la terre et parafoudres. Les connaissances acquises dans cette thèse indiquent clairement que les influences de la foudre non verticale doivent être prises en compte pour une évaluation précise des surtensions induites par la foudre. Pour (2), les circuits du modèle FDTD sont validés par rapport aux résultats expérimentaux dans des articles publiés, et les influences de la distance de la foudre, de la position de la foudre sur la ligne, de la structure de mise à la terre, de la position du fil neutre, etc. sont étudiées par la FDTD. Il est confirmé que le couplage électromagnétique foudre-terre influence le courant de surface de la terre et l'augmentation du potentiel de terre (GPR) qui en résulte pendant une période transitoire, et donc l'inclinaison de la foudre rend le courant et le GPR différents du cas vertical.  ABSTRACT: Lightning induced overvoltages are becoming one of the most important topics in the field of distribution networks. An accurate evaluation of the induced voltages is essential for the design of lightning protection. One problem of existing evaluations is that a vertical lightning channel and a perfectly conducting earth, which are not realistic, are assumed in most cases. These assumptions require further careful investigations for an accurate induced-voltage evaluation.  The main objective of this thesis is to reveal and summarize (1) the influences of non-vertical lightning on the lightning induced overvoltages in the distribution systems and (2) lightning current behavior in a lossy earth, for an accurate evaluation of the induced voltages.  For (1), FDTD model circuits to represent the non-vertical lightning are built and influences of the non-vertical lightning on the induced voltages are investigated with various conditions such as lightning current waveform, lightning-channel geometry, earth condition, and distribution-line configuration etc. In addition, the mechanism of the changes is discussed in comparison with an analytical formula. It is made clear that lightning inclination toward the line significantly increases the induced voltages. The voltages reach values that are more than two times larger than those of the vertical case. The inclination along the line shows only minor differences on the peak voltage while it makes the voltage profile along the line asymmetric. Similar trends are observed even when a realistic three-phase line with groundings and arresters is assumed. The knowledge obtained in this thesis clearly indicates that the influences of non-vertical lightning should be considered for an accurate evaluation of lightning induced overvoltages.  For (2), FDTD model circuits are validated in comparison with experimental results in published papers, and influences of lightning distance, lightning-struck position to the line, grounding structure, neutral wire position etc. are investigated by FDTD. It is confirmed that lightning-to-earth electromagnetic coupling influences the earth surface current and resulting ground potential rise (GPR) in a transient period, and thus the lightning inclination makes the current and GPR different from the vertical case. The coupling effect should be considered for accurate earth current and GPR studies. When there is a distribution line nearby, a large portion of lightning current flows into the nearby line via its groundings. Although the current itself does not make a large difference to the induced voltage, it would cause lightning surge problems in the line.


identifier: Recchia, G. (2020). Conception et validation d'outils pour injection sur profil aérant  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Ce mémoire a pour objectif de présenter la conception, la réalisation et le test d'outils expérimentaux dans le but d'obtenir un profil d'aile dit “aérant”. L'aération des turbines hydroélectriques est aujourd'hui une problématique de recherche qui se développe de plus en plus. En effet, d'une part elle serait une bonne manière d'atteindre les normes environnementales en vigueur et d'autre part, constitue une avancée technique capable d'améliorer la durée de vie des turbines actuelles voire même, sous certaines conditions précises, d'accroître leurs performances en rendement. La réalisation d'un profil aérant, qui se rapproche du profil d'une aube de turbine, capable d'injecter de l'air dans un écoulement d'eau à haute vitesse (de 10 à 25 m/s) constitue un pas de plus vers la compréhension des phénomènes qui ont lieu dans les turbines aérantes et sont justement étudiés au sein de la Chaire CRSNG-GE à Polytechnique Montréal. Dans ce mémoire il sera détaillé, dans un premier temps, les simulations pour optimiser la chambre à air interne du profil et la conception du profil lui même. Les simulations ont permis d'obtenir une chambre à air garantissant un profil de vitesse de l'air en sortie le plus homogène possible pour des conditions de pleines charges (injections de 55 L/s d'air dans la boucle) avec une vitesse moyenne de sortie de l'air de 135 m/s dans la veine d'essai. Le travail présenté ici fait également part de la construction d'une toute nouvelle boucle pour accueillir les tests préliminaires à basse vitesse du profil ainsi que les autres expériences à basses vitesses de la Chaire. Des instruments de mesure propres à cette boucle ont également été développés, dont un nouveau système de déplacement motorisé pour les sondes à fibres optiques et un ensemble de jauges de contraintes pour le profil. Ces dernières se révéleront utiles pour la suite des expériences afin de quantifier les efforts en jeu sur le profil sous différentes conditions d'écoulements. La technique de “Krigeage” développée au long de cette Maîtrise permet de lisser les résultats et, dans une moindre mesure, d'obtenir des cartographies 3D de l'écoulement à partir de données 2D. Ce modèle reste néanmoins à développer plus en profondeur afin d'en tirer une utilisation optimale. Les tests préliminaires font état d'un bon comportement du profil aérant à basse vitesse et laissent entrevoir de très bonnes perspectives lorsque que ce dernier sera mis en écoulement à haute vitesse.  ABSTRACT: This thesis presents the design, realisation and testing of an aerating profile and devices to test and understand the behaviors of the latter. The aeration of hydroelectric turbines is today a research field that is growing. Indeed, it would be a good way to achieve the environmental standards in terms of water oxygenation. Moreover it is a technical advance capable of improving the lifetime of current turbines or even, under certain specific conditions, to increase their efficiency. Thus, the tests of an “aerating” profile , similar to the profile of a turbine blade, and capable of injecting air into a high-speed water flow (from 10 to 25 m/s) represent a further step towards understanding the phenomena that occur in aerating turbines and are currently studied within the NSERC-GE Chair at Polytechnique Montreal. In this thesis we expose the simulations to optimize the inner air chamber of the profile and the design of the profile. The simulations allowed us to design an air chamber that produce a most homogeneous air velocity profile for full load conditions (injections of 55 L/s of air into the water loop) with an average air velocity of 135 m/s into the test section. The work presented here also includes the construction of a completely new loop to accommodate the preliminary low-speed tests of the profile as well as the other low-speed experiments of the Chair. Measuring instruments specific to this loop have also been developed, including a new motorized displacement system for fiber optic probes and a set of strain gauges for the profile. These will be useful for further experiments in order to quantify the loads involved on the profile under different flow conditions. The technique of “Krigeage" developed along this Master allows to smooth the results and to obtain 3D mapping of the flow from 2D data. However, this model still needs to be developed in order to get its full potential in terms of representativity of the void fraction. Preliminary tests yield a good behavior of the low-speed air profile and suggest very good prospects for high-speed velocities tests.


identifier: Dhar, L. (2020). Étude de l'injection d'air à travers des fentes dans un écoulement d'eau transverse  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Ce mémoire étudie l'injection d'air à travers des fentes de formes différentes dans un écoulement d'eau transverse. Peu d'informations sont disponibles à ce sujet quand bien même l'injection d'air a déjà été largement étudiée pour des eaux stagnantes et pour de faibles débits d'injection d'air pour des injecteurs circulaires. L'objectif de ce projet est de déterminer les conditions optimales d'injection d'oxygène dans les conduites des centrales hydroélectriques. L'intention est d'éviter d'affecter négativement la vie aquatique en aval des centrales causée par l'appauvrissement en oxygène de l'eau rejetée. Pour mener à bien la recherche sur ce sujet, il est nécessaire d'injecter un grand débit d'air dans un écoulement d'eau. L'étude présentée ici vient compléter des travaux précédents. Elle consiste à prendre des mesures dans les installations expérimentales qui permettent d'injecter de l'air à débit réglable à travers des fentes interchangeables dans un écoulement d'eau dont on peut également contrôler le débit. Les mesures sont effectuées grâce à l'insertion d'une sonde optique dans l'écoulement. Les résultats obtenus à l'aide de la sonde optique permettent d'étudier la vitesse et la taille des bulles ainsi que le taux de vide. L'analyse des données met en avant l'augmentation de la vitesse des bulles le long de l'écoulement. Les distributions des tailles et vitesses des bulles suivent des loi log-normales. De plus, le nuage de bulles est stratifié; les grosses bulles s'élèvent vers le haut du nuage tandis que les plus petites restent proches de la paroi inférieure. Des bulles plus grosses et plus rapides sont obtenues en augmentant le débit d'air à débit d'eau constant et faible. Ensuite, les graphes montrent une diminution du taux de vide local en s'éloignant de l'injection. Ces résultats sont complétés par le Krigeage qui est une méthode d'interpolation qui permet de tracer les cartes de taux de vide dans toute la veine à partir de quelques plans de mesures. Les différentes conclusions de cette étude permettent de faire un pas de plus vers la compréhension du comportement de l'écoulement diphasique dans la veine d'essai, compréhension encore largement incomplète. Pour limiter le côté chrono-phage de la prise de mesure, une nouvelle version motorisée de la sonde optique a été conçue, fabriquée et testée. Elle permet, ainsi que tous les travaux effectués, de donner les outils pour les prochaines expériences à effectuer dans le laboratoire expérimental de grande hauteur. Celui-ci permettra d'aller à des vitesses d'écoulement beaucoup plus grandes que celles testées dans cette maîtrise.  ABSTRACT: This thesis presents work related to the injection of air through different slot geometries in a cross-flow. The project aims to optimize the injection of air in hydraulic turbines to meet the national and international standards with regards to water aeration. These standards aim at ensuring that released water from hydroelectric plants to be depleted in oxygen and affect aquatic life. To study this topic, an existing experimental set-up was used for various water and air flow rates. Two different slot geometries were tested for one flow speed. Measurements of the pressure in the injection chamber and the test section were possible. An optical probe was used to determine void fraction but also bubble sizes and velocities on three different planes transverse to the flow downstream of the injection site. Different results were analyzed and many conclusions drawn. First of all, the air passing through the slot experiences a pressure change that scales to the cube of the air flow rate whether there is water or not on the other side. The multiplying factor changes with the geometry of the injection. Moreover, bubble speed and size follow log-normal distributions. The size of bubbles increases with an increase in the air flow rate. Bigger bubbles travel faster than small ones ; they also tend to rise to the top of bubble plume while small bubbles stay in the lower section. The maps of void fraction show that its local values decrease for a smaller air flow rate. Those values also drop while moving away from the injection slot. Due to the time-consuming aspect of the measurements, a new motorized version of the optical probe was designed, manufactured and tested. It is also adapted to the test sections of the new laboratory where high-speed flows can be tested.


identifier: Zarpellon, G. (2020). Machine learning algorithms in Mixed-Integer Programming  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: De nombreux problèmes de la vie courante comportent des décisions discrètes, et peuvent être modélisés sous la forme de programmes d'optimisation en nombres entiers. De tels modèles peuvent désormais être résolus efficacement à l'aide de solveurs matures comportant un vaste arsenal algorithmique, ce qui explique l'utilisation quotidienne de la programmation mathématique mixte en nombres entiers (PNE) dans de multiples secteurs. Alors que les techniques d'apprentissage automatiques (à partir d'exemples) sont de plus en plus mises en œuvre pour l'analyse de données et la predicion, une attention nouvelle est donnée à l'apprentissage dans le contexte d'algorithmes d'optimisation, notamment dans les choix algorithmiques des solveurs de PNE. Cette thèse s'inscrit dans ce courant de recherche : nous analysons et proposons de nouvelles méthodes pour intégrer des techniques d'apprentissage automatique au sein d'algorithmes d'optimisation, et explorons le potentiel de cette interaction. Premièrement, nous passons en revue l'état de l'art quant à l'utilisation de techniques d'apprentissage automatique pour la sélection de variables et de nœuds dans un arbre de branchement. Plusieurs travaux de PNE sont identifiés comme précurseurs d'approches basées sur l'apprentissage automatique. En discutant les hypothèses et questions sousjacentes de ces décisions, nous proposons un nouveau cadre pour analyser les approches récentes d'apprentissage, et soulignons des nouvelles perspectives quant à l'utilisation de l'apprentissage pour guider le branchement. Deuxièmement, nous développons un modèle de classification pour identifier si un programme d'optimisation quadratique convexe avec variables mixtes doit être linéarisé ou non. En particulier, cette approche vise à exploiter, au sein du processus d'apprentissage, la connaissance de l'algorithme d'optimisation. Comme le montre l'implémentation au sein du solveur IBM-CPLEX, ces travaux décrivent plus largement une méthodologie pour combiner des technologies d'apprentissage et de PNE. Troisièmement, nous employons une approche basée sur la classification des séries temporelles pour prédire, après avoir utilisé une fraction du temps de calcul alloué, si un problème de PNE sera résolu ou non dans le temps imparti par l'utilisateur. Plus généralement, ces expériences sont un point de départ pour explorer comment des algorithmes d'apprentissage automatique peuvent utiliser l'information du processus de branchement pour en identifier les tendances, et éventuellement influencer la résolution. Enfin, nous présentons un nouveau cadre d'apprentissage par imitation pour le problème de sélection de variable dans un arbre de branchement. Afin d'obtenir des stratégies de branchement pouvant être généralisées à des instances de PNE génériques, nous introduisons un nouveau modèle d'aprentissage qui prend en compte l'évolution de l'arbre de branchement et le rôle des variables candidates. En plus d'atteindre les performances recherchées, cette approche offre de nouvelles bases pour de futures recherches sur les algorithmes de branchement.  ABSTRACT: A variety of real-world tasks involve decisions of discrete nature, and can be mathematically modeled as Mixed-Integer Programming (MIP) optimization problems. Daily deployed in multiple application domains, MIP formulations are nowadays solved effectively and reliably, thanks to the complex and rich algorithmic frameworks developed in modern MIP solvers. With machine learning (ML) being extensively leveraged to “learn from examples”, new attention has been given to the application of learned predictions in optimization settings, especially in the context of MIP solvers' algorithmic design. The present thesis contributes to this thread of research: we discuss and propose novel methods on the theme of using ML algorithms alongside MIP ones, and explore some opportunities of this fruitful interaction. First, to document ML attempts addressing the decisions of variable and node selection in Branch and Bound (B&B), we present a survey on learning and branching. By interpreting previous MIP literature contributions as forerunners of ML-based works, and discussing the assumptions and concerns underlying these critical heuristic decisions, we provide an original canvas to analyze recent learned approaches and outline new points of view. Second, we develop a classification framework to tackle the algorithmic question of whether to linearize convex quadratic MIPs, aiming at a tight integration of the optimization knowledge in the learning pipeline. As experiments practically led to the deployment of a classifier in the IBM-CPLEX optimization solver, the work more generally outlines a reference methodology for the combination of ML and MIP technologies. Third, we employ a feature-based sequence classification approach to predict, after only a fraction of the available computing time has passed, whether a MIP will be solved before time-limiting. From a broader perspective, the experiments represent a starting point for exploring how statistical learning algorithms could utilize data from B&B to identify trends in MIP optimization, and possibly influence the resolution process. Finally, we contribute a novel imitation learning framework for variable selection. With the goal of learning branching policies that generalize across generic MIP instances, we introduce a new architectural paradigm that places at its center the evolution of B&B search trees and the role of candidate variables within it. On top of establishing the sought generalization capabilities, the approach offers fresh and promising ideas for future research on branching.


identifier: Lévesque, F. (2020). Lignes du temps connectées pour l'analyse visuelle d'adaptations et de relations entre artistes  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: de l'artiste). Les listes d'artistes énumèrent les artistes qui ont inspiré, collaboré ou se sont inspirés de l'artiste. La notice de chanson affiche des informations supplémentaires sur une chanson sélectionnée. Le résumé de l'artiste donne une vue globale sur les rôles occupés et les types de productions de l'artiste.  ABSTRACT: The rise of Linked Open Data in the recent years is  emocratizing access to complex data structures, usually taking the form of very large multivariate graphs. These are typically hard to understand for humans and require the use of visualization tools. While this data structure is a very well-researched topic in data visualization, large and complex graphs — with several heterogeneous node and link attributes — are hard to visualize with existing techniques. During a project in collaboration with the national library and archives agency of the Quebec government, we have been mandated to visualize a complex dataset of relationships between artists. Eleven key exploratory tasks were selected during the initial design process. Standard graph visualization techniques weren't suited to answers those specific tasks. Furthermore, since the dataset's structure is an unusual combination of a bipartite graph and trees, a thorough literature review found very few related or similar work. This research proposes a novel visualization method called MuzLink to efficiently explore and discover relationships between artists. The objective is to evaluate the effectiveness of this method for the selected task with a formal user study. Based on all eleven selected tasks, a fully functional prototype was developed. The proposed solution is a multi-facet visualization tool centered around a specific artist. The first view contains 3 connected timelines: (1) the inspirations, (2) the productions, and (3) the influences. Beeswarms of songs are positioned on the timelines according to their relationship with the artist. Songs on the middle timeline are the artist's production. Songs that inspired the artist are on the top timeline. Songs inspired by the artist are on the bottom timeline. Links are drawn between songs having an influence relationships. This connected timeline allows a topological exploration of inspiration relationships around an artist's musical production. The second view shows inspired, collaborators, and influenced artists ordered by their number of implications with the current artist. Interactions between the two complementary views allow answering a larger range of tasks. The user can easily navigate between artists with a search bar and by clicking on related artists. Clicking on a song reveals more details regarding the relationships among other songs.


identifier: Moins, T. (2020). Modèle hybride combinant réseau de neurones convolutifs et modèle basé sur le choix pour la recommandation de sièges  [Mémoire de maîtrise, Polytechnique Montréal].

abstract: RÉSUMÉ: Avec la vente de billets en ligne, les consommateurs souhaitant réserver un ticket pour un concert, une pièce de théâtre ou un film ont désormais la possibilité de choisir leur emplacement. Ce choix influence l'expérience vécue : différents facteurs sont à considérer, et chaque client fait son propre raisonnement (plus ou moins consciemment) pour prendre cette décision. Par exemple, dans un cinéma, certaines personnes vont privilégier les sièges au centre pour avoir la meilleure vision possible de l'écran, tandis que d'autres pourront préférer les sièges latéraux pour être moins dérangés par la présence d'autrui, en particulier si beaucoup de sièges au centre sont déjà réservés. Cet exemple illustre l'hétérogénéité de raisonnement d'un consommateur dans cette situation, et met en valeur deux catégories de facteurs influant sur la prise de décision : la position dans la salle, et la proximité aux autres. La réservation en ligne a ainsi permis de collecter ces choix dans des bases de données, et pour l'industrie culturelle (dans notre exemple le gérant de cinéma), cette information peut être cruciale. D'abord, connaître les sièges les plus attractifs à un instant donné peut permettre de modifier la tarification et ainsi augmenter l'affluence dans les salles et donc les recettes. De plus, si cette connaissance se fait spécifiquement pour chaque utilisateur ayant déjà effectué des réservations par le passé, cela peut également permettre d'améliorer les stratégies marketing par la mise en place d'un système de recommandation personnalisé de sièges. Un premier objectif du mémoire est la revue de méthodes permettant l'estimation de l'attractivité d'un siège dans une salle partiellement remplie. Deux stratégies sont possibles : la première consiste à traiter chaque client individuellement afin d'assurer une modélisation personnelle de la prise de décision, mais qui est limité par la quantité de données disponible par clients. L'autre stratégie consiste à regrouper l'ensemble des données pour pouvoir appliquer des modèles avec plus de capacité comme de l'apprentissage profond, mais qui perd l'information du comportement individuel. Une hypothèse de ce mémoire est que malgré une performance plus faible pour la deuxième stratégie, cette dernière apporte de l'information utile, et une combinaison des deux permet d'améliorer la performance globale et de pallier au problème de la stratégie individualisée du possible manque de données.  ABSTRACT: With online ticket sales, consumers wishing to book a ticket for a concert or a movie now have the opportunity to choose their location. This choice influences the lived experience: different factors have to be considered, and each client makes his own reasoning (more or less consciously) to make this decision. For example, in a movie theatre, some people may prefer centre seats to get the best possible view of the screen, while others may prefer side seats to be less disturbed by the presence of others, especially if many centre seats are already reserved. This example illustrates the heterogeneity of reasoning of a consumer in this situation, and highlights two categories of factors influencing decision making: position in the room, and proximity to others. Online booking has thus made it possible to collect these choices in databases, and for the cultural industry, this information can be crucial. Firstly, knowing the most attractive seats at a given time can help to modify the pricing and thus increase attendance in halls and thus revenues. Moreover, if this knowledge is done specifically for each user who has made reservations in the past, it can also help improve marketing strategies by implementing a personalized seat recommendation system. A first objective here is the review of methods for estimating the attractiveness of a seat in a partially-filled room. Two strategies are possible: the first one is to treat each client individually to ensure personal modeling of decision making, but this is limited by the amount of data available per client. The other strategy is to aggregate the data to be able to apply models with more capacity such as deep learning, but lose the information about individual behaviour. One hypothesis of this paper is that despite weaker performance for the second strategy, the latter provides useful information, and a combination of the two can improve overall performance and overcome the problem of the individualized strategy of the possible lack of data.


identifier: Vautrin, Y. (2020). Modélisation et simulation numérique d'écoulements diphasiques de fluides séparés par une interface avec une méthode d'éléments finis adaptatives en espace et en temps  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Nous présentons dans ce mémoire les développements qui ont été réalisés afin de mettre en place des modèles et des méthodes permettant de simuler numériquement des problèmes d'écoulements diphasiques de fluides séparés par une interface avec une méthode d'éléments finis adaptative en espace et en temps sur des domaines bidimensionnels. Nous proposons pour cela une méthodologie conçue de façon à simultanément « calculer juste et au juste coût ». La réalisation de ces deux objectifs repose respectivement sur l'utilisation (1) de modèles représentatifs de la physique des écoulements diphasiques à phases séparées et de méthodes numériques à ordre élevé très précises, et (2) de méthodes adaptatives en espace et en temps. L'approche développée se base sur l'utilisation d'une méthode de suivi d'interface dans laquelle les interfaces qui séparent deux fluides non miscibles sont représentées explicitement au sein du maillage du domaine de calcul. Cette méthode permet de représenter fidèlement et avec une grande précision les phénomènes se produisant dans la région interfaciale mais nécessite de déformer le maillage pour suivre les déplacements des interfaces. La méthode du pseudo-solide et une formulation Arbitrary Lagragian-Eulerian (ALE) des équations de Navier- Stokes fournissent dans notre implémentation une manière robuste et efficace d'effectuer la déformation du maillage. Les activités de modélisation de la physique sont concentrées sur deux aspects fondamentaux pour les écoulements diphasiques à phases séparées : (1) la modélisation de la force de tension superficielle et du comportement de la ligne de contact, et (2) la prise en compte de la compressibilité des fluides. Nous avons implémenté pour cela une formulation de la tension superficielle qui, grâce à l'utilisation de l'opérateur de Laplace-Beltrami, est parfaitement compatible avec la méthode des éléments finis. Deux modèles pour la compressibilité des fluides nous permettent par ailleurs de représenter le comportement des gaz et des liquides faiblement compressibles. L'approche adaptative en espace et en temps assure d'une part que l'erreur de discrétisation est connue et contrôlée tout au long de la simulation et d'autre part que le coût de calcul est aussi faible possible pour atteindre la précision demandée par l'utilisateur. L'algorithme d'adaptation de maillage pour les simulations instationnaires et la méthode de remaillage que nous avons développée contribuent par ailleurs à minimiser la charge de travail de l'utilisateur et permettent d'automatiser et de rendre autonome l'ensemble de la chaîne de calcul. La réalisation de simulations de vérification et de validation permet de confirmer que les différents modèles et méthodes numériques utilisés sont correctement implémentés et fournissent une représentation correcte de la physique des problèmes auxquels nous nous intéressons. Le processus de vérification basé sur l'utilisation de la méthode des solutions manufacturées (MMS) permet de confirmer que l'implémentation des équations est correcte. La validation des modèles est ensuite réalisée en confrontant les résultats obtenus numériquement à des données issues de modèles analytiques simples. Enfin, nous illustrons les capacités de la chaîne de calcul complète en réalisation la simulation de différents phénomènes qui sont typiquement rencontrés dans les problèmes d'écoulements diphasiques à phases séparées : instabilités de Rayleigh-Taylor et de Kelvin-Helmholtz et ascension d'une bulle de gaz sous l'effet de la poussée d'Archimède. Un cas plus complexe représentant l'impact d'une vague déferlante sur une paroi solide met par ailleurs en oeuvre l'ensemble des développements réalisés. Ces simulations mettent en évidence que les algorithmes employés sont capables de capturer et représenter efficacement à la fois les déplacements et déformations à grande échelle des interfaces mais aussi les phénomènes à haute fréquence et ayant une petite échelle spatiale. Les comparaisons des résultats issus de ces simulations à des résultats théoriques, expérimentaux et numériques indique que notre formulation est capable de fournir des données très précises pouvant être utilisées pour la conception de systèmes complexes ou l'étude de phénomènes physiques fondamentaux.  ABSTRACT: This work presents an adaptive in space and time approach for the simulation of twodimensional unsteady interfacial flows based on the finite element method that takes into account the influence of surface tension. Our proposed solution relies on models and numerical methods that are able to provide accurate results in a cost-efficient manner. Achieving these two objectives is done through the joint use of (1) accurate models for the physics of interfacial flows and high-order numerical methods, and (2) adaptive numerical methods in space and time. The approach we have developed takes advantage of an interface tracking method in which the interfaces separating two immiscible fluids are explicitly represented within the mesh of the computational domain. This method allows us to accurately represent and capture the various phenomena occurring in the interfacial region but requires the computational grid to be deformed in order to track the displacements of the interfaces. The pseudo-solid method and an Arbitrary Lagragian-Eulerian (ALE) formulation of the Navier-Stokes equations provide, in our implementation, a robust and efficient way to perform mesh deformation. Modeling activities are focused on two fundamental aspects for separated two-phase flows: (1) modeling surface tension effects and the behavior of the moving contact line, and (2) taking into account the influence of fluid compressibility. The formulation of the surface tension force we have implemented provides, thanks to the use of the Laplace-Beltrami operator, an accurate formulation that is fully compatible with the finite element method. Compressibility effects in gases and nearly incompressible liquids are modeled using two distinct equations of state. The adaptive approach in space and time ensures that, on the one hand, the discretization error is known and controlled throughout the simulation and, on the other hand, that the computational cost is as low as possible to achieve the user-requested accuracy. The mesh adaptation algorithm for unsteady simulations and the remeshing method that we have developed additionally minimize the user's workload and automate the entire simulation process. Verification and validation simulations are performed to confirm that the various models and numerical methods used are correctly implemented and provide a correct representation of the physics of the problems of interest. The verification process based on the use of the Method of Manufactured Solutions (MMS) allows us to confirm that the implementation of the equations and methods has been done correctly. The validation of the models is then carried out by comparing the results obtained numerically with data derived from simple analytical models. Lastly, we illustrate the capabilities of our approach with the simulation of various phenomena typically encountered in two-phase flow problems: Rayleigh-Taylor and Kelvin-Helmholtz instabilities and the rise of a gas bubble due to buoyant forces. A fourth and more complex case representing the impact of a breaking wave on a solid wall demonstrates the simultaneous use of all the developments carried out in this project. These simulations show that the algorithms used are capable of efficiently capturing and representing both large-scale displacements and deformations of the interfaces, as well as high-frequency, small-scale phenomena. Comparisons of the data extracted from these simulations with theoretical, experimental and numerical results show excellent agreement, suggesting that our formulation provides very accurate and physically meaningful results that can be used to design complex systems or to study fundamental physical phenomena.


identifier: Lakhdissi, E. M. (2020). Hydrodynamics and Mass Transfer of Two-Phase and Three-Phase Bubble Column Reactors  [Thèse de doctorat, Polytechnique Montréal].

abstract: RÉSUMÉ: Les colonnes à bulles (gaz-liquide) et les colonnes à bulles à suspension (gaz-liquide-solide) sont connues comme l'un des types de réacteurs polyphasiques les plus utilisés dans l'industrie et qui traitent les matières premières renouvelables ainsi que les ressources fossiles conventionnelles. Plusieurs procédés chimiques, pétrochimiques, biochimiques, alimentaires, pharmaceutiques et de capture de dioxyde de carbone sont effectués dans des colonnes à bulles. Ils sont sélectionnés parmi d'autres contacteurs gaz-liquide car ils offrent des avantages uniques, en l'occurrence des faibles coûts de maintenance et d'exploitation, une facilité d'utilisation et des taux de transfert de chaleur et de masse élevés.  ABSTRACT: Bubble columns (gas-liquid) and slurry bubble columns (gas-liquid-solid) are known as one of the most utilized commercially types of multiphase reactors that treat renewable feedstocks as well as conventional fossil resources. Several chemical, petrochemical, biochemical, food, pharmaceutical, and carbon dioxide capture processes are carried out in bubble columns. They are selected among other gas-liquid contactors since they offer some unique advantages such as low maintenance and operating costs, ease of operation and high heat and mass transfer rates.