identifier: Basty, D. R. (2017). Impacts des politiques énergétiques sur la sélection des stratégies durables de bioraffinage forestier  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: L'industrie forestière canadienne étant en perte de vitesse; sa position qui, autrefois concurrentielle, semble être de plus en plus menacée par la montée fulgurante de la compétition internationale, qui plus est, est au profit des économies émergentes comme la Chine, l'Inde et bien d'autres, —toutes considérées comme des bassins d'une main-d'oeuvre qualifiée, mais à faibles coûts. La remise sur pied de cette industrie nécessiterait la considération de nouvelles stratégies viables et durables. Cependant, la relation étroite et privilégiée qu'a l'industrie forestière avec les localités et les communautés rurales exige que celle-ci fasse des choix durables. Ces choix doivent considérer les enjeux climatiques actuels, les enjeux économiques, les enjeux environnementaux et les enjeux sociaux sans pour autant oublier la prise en compte des lois et règlements aussi bien actuels qu'à venir relatifs aux initiatives de lutte contre le changement climatique. Les acteurs dans le secteur forestier ont un faible intérêt lorsqu'il s'agit de politiques; par conséquent, le secteur préfère se distancer de toute forme de dépendance à l'égard des subventions et autres politiques gouvernementales. Ce point de vue est soutenu par le récent sondage auprès d'un groupe consultatif composé d'intervenants, acteurs et expert industriels, du secteur forestier canadien et américain. Le groupe a été invité à prendre connaissance d'une liste contenant des facteurs et barrières soigneusement sélectionnés. Par la suite, le groupe a été invité à évaluer l'importance de cet ensemble de facteurs et de barrières, et d'expliquer comment ces facteurs et barrières entrent en compte dans leur prise de décision pour la mise en oeuvre et l'implantation des technologies de bioraffinerie. Les facteurs et barrières en lien (dénotant) les enjeux et les politiques du gouvernement ont reçu une très faible pondération de la part du groupe. Les auteurs du sondage ont conclu que x l'industrie veut garder son indépendance à l'égard des politiques (instruments), mais en même temps, elle veut savoir en détail, quelles sont les politiques en cours et quelles orientations vont prendre ces politiques à court terme. — Ce qui leur permettrait d'atténuer les risques relatifs. Toutefois, les experts dans le domaine de l'énergie et des politiques climatiques estiment que les instruments politiques sont essentiels pour mieux cadrer la transition énergétique et la transition vers une économie à faible teneur en carbone. À mesure que les initiatives et les politiques gouvernementales en matière de changement climatique continuent de promouvoir la transition vers une bioéconomie, en favorisant le développement des bioproduits et les technologies, le secteur forestier ne peut pas rester en marge de cette dynamique. Ces experts pensent que les entreprises existantes seront confrontées à la concurrence de la part de nouveaux acteurs qui profiteront d'une bonne compréhension des occasions favorables associées aux futures politiques énergétiques et climatiques. Par conséquent, les chefs d'entreprise dans le secteur forestier ne devraient pas attendre que les politiques soient clairement établies, mais devraient anticiper les nouvelles politiques en observant et en analysant leur environnement d'affaires. Un regard avisé devrait leur permettre de prendre conscience des possibles changements à venir et connaître la direction que le gouvernement pourra donner à ses prochaines politiques. Ils peuvent alors tirer un avantage stratégique des circonstances opportunes résultantes de ces nouvelles ou futures politiques, une fois qu'elles auront été mises en oeuvre. L'objectif de cette étude est de développer un cadre méthodologique qui utilise un ensemble d'outils d'ingénierie des systèmes incluant l'analyse et la simulation des procédés, l'analyse de cycle de vie (ACV), l'analyse techno-économique (ATÉ) et l' analyse multicritère décisionnelle (AMCD) afin 1) d'évaluer la viabilité des stratégies de bioraffinerie; et 2) d'examiner à quel point les instruments politiques peuvent influencer la planification stratégique et la prise de décision à l'échelle d'une compagnie, d'une usine de pâtes et papiers par exemple. La méthodologie comporte deux phases à savoir la Phase I et la Phase II. La Phase I est composée de 3 étapes. Premièrement, un ensemble de stratégies de bioraffinerie (c'est-à-dire une combinaison de procédés / produits) qui a un fort potentiel d'intégration est défini. Deuxièmement, les performances environnementales et économiques des stratégies sont évaluées à l'aide d'une analyse du cycle de vie et d'une d'analyse techno-économique. Troisièmement, un ensemble de critères est développé pour permettre de classer et de sélectionner les stratégies préférables. Les résultats obtenus de la phase I constituent une base de données pour Phase II. La phase II est, elle aussi, composée de trois étapes. Premièrement, sur la base d'une revue de littérature, les instruments politiques jugés essentiels au développement de la bioéconomie sont sélectionnés et utilisés comme intrants économiques dans le cadre méthodologique. Deuxièmement, les impacts potentiels de ces instruments sur la mise en oeuvre des stratégies de bioraffinerie sont évalués à l'aide de la plate-forme modélisation intégrée. Troisièmement, en utilisant un système matriciel et les critères de décision, les stratégies de bioraffinerie sont à nouveau classées selon leurs scores globaux, et ce nouveau classement est comparé au classement obtenu dans la phase I. En d'autres mots, les préférences obtenues sous la considération des instruments de politique sont comparées aux préférences initiales des décideurs obtenues dans les conditions de base (sans aucune considération de politiques). La méthodologie a été appliquée dans le cadre d'une étude de cas concrète. Les instruments politiques ont été intégrés dans le cadre afin d'évaluer la décision concernant la sélection des stratégies préférées de bioraffinerie forestière. De prime abord, il était attendu (par les experts à l'usine) que : si les projets de bioraffinerie généralement reconnus pour leurs coûts élevés en capital étaient subventionnés à travers différents instruments de politiques, ces projets auraient de meilleures performances que les projets à faible intensité capitalistique. Malheureusement, même hauteur de 50% de subvention en coûts d'investissement, le projet le plus onéreux n'a pas été en mesure de produire de bonnes performances économiques que les autres stratégies ayant de faibles coûts d'investissement. Cela signifie que la diversification des flux de revenus est également une composante importante dans la performance économique des projets de bioraffinerie. Ainsi, les projets à coûts élevés en capital ne devraient pas se baser uniquement sur les subventions à l'investissement, mais devraient également développer des approches novatrices et des moyens de cibler des segments de marchés bien déterminés, en ciblant par exemple la production des produits à faible volume, mais à très hautes valeurs ajoutées. Cependant, lorsque les instruments de politique sont combinés en tant que scénarios de politiques, le taux de rendement interne (TRI) de toutes les stratégies est doublé par rapport au cas de base (sans considération politique). Le système matriciel qui intègre les performances issues de l'analyse des scénarios politiques dans un modèle de prise de décision montre à quel point les scores globaux et le classement des stratégies préférées de bioraffinerie changent d'ordre sous certains scénarios de politiques. En effet, lors de l'analyse économique du cas de base, la stratégie de bioraffinerie ayant affiché un fort coût d'investissement a été classée comme la moins préférée parmi les stratégies de bioraffinerie (stratégie disqualifiée). Toutefois, sous la considération des scénarios (combinaison d'instruments), ladite stratégie devient la deuxième stratégie la plus préférée (classée deuxième) sous certains scénarios. Cette analyse a montré que les politiques peuvent influencer les décisions stratégiques. De plus, l'analyse montre que le gouvernement pourrait favoriser le développement des bioproduits grâce à divers instruments, y compris les instruments fiscaux, les subventions à l'investissement, etc. Le soutien du gouvernement peut servir de levier pour la bioéconomie et pour la mise au point de nouveaux segments de marché. Ces résultats auront une application directe dans le secteur de l'industrie forestière, et aideront les entreprises forestières à comprendre l'aspect compétitif et subtil des attributs non tarifaires de la bioéconomie (économie à faible teneur en carbone). En effet, avec la déclaration environnementale de produits (DEP), l'empreinte carbone, les perceptions sociales, et d'autres mesures qui sont certes des attributs non tarifaires (pour l'instant), mais peuvent devenir sources de barrières tarifaires. Cela étant dit, il est essentiel pour les entreprises de prendre en compte ces attributs dès maintenant, afin de demeurer compétitif et attractif à l'international surtout sous la houlette des accords de libres-échanges tels que l'accord de libre-échange nord-américain (ALÉNA), le partenariat transpacifique (PTP), et plus récemment, l'accord économique et commercial global (AECG). En utilisant une approche de planification telle que celle proposée dans cette thèse, les entreprises forestières (1) pourront anticiper des changements dans l'environnement réglementaire plutôt que de réagir à ceux-ci, après coup; et (2) elles seront mieux préparées et mieux équipées pour agir stratégiquement en réponse aux annonces de futurs règlements, de futures mesures et bien d'autres politiques gouvernementales.  ABSTRACT: The Canadian forestry sector has experienced significant economic challenges that have affected its competitive position in the global market. For this industry to thrive and regain its position, new bioeconomy strategies should be considered. Among these, the forest biorefinery has emerged as an excellent candidate. Alongside the global economic challenges, global warming and more specifically, greenhouse gas (GHG) emission reductions are key drivers in promoting a shift to the bioeconomy. Thus, when designing and selecting a sustainable biorefinery strategy, both issues must be considered, as well as the dynamic and seasonal aspects of a bioeconomy market and implemented policies. Stakeholders in the forest sector have a low-interest when it comes to policies; therefore, the sector minimizes its reliance on government policy. That claim is supported by the recent panel workshop, in which a group of industrial stakeholders, from both the Canadian and US forest sector, was asked to assess the importance of a set of drivers and barriers in their decisionmaking for the implementation of biorefinery strategies. This group of stakeholders gave low importance to the policy-related driver and barrier. The authors concluded that industry wants to be independent of policy, but at the same time wants to know in detail what policies are in the making, thereby mitigating policy risk. However, experts in the field of energy and climate policies believe that policy instruments are essential in the transition to a low-carbon economy. As initiatives and government policy around climate change continue to promote the transition to a bio-based economy by promoting low-carbon technology and bio-based product development, the forestry sector cannot remain on the sidelines. They believe that existing companies will face competition from new players who will take advantage through a good understanding of the opportunities associated with future energy and climate policies. Therefore, business leaders in the forestry sector should not wait for a clearly established policy, but should anticipate new policies by scanning and analyzing changes in the policy framework and business environment. They may then take strategic advantage of the opportunities that result from new policies once they have been implemented. The forestry sector has a unique position due to its competitive access to biomass, and it can strengthen its position as a sustainable and major provider of fibre, energy (including electricity), chemicals and materials to meet the world's growing needs. Furthermore, the sector could be a major supplier of ecosystem services—the valuable benefits provided by nature—such as carbon storage and sustainable forest-based products. However, in particular the Canadian forestry sector lags behind with advanced bioproduct development due to a lack of financial capital. Therefore, government support through different policy instruments (i.e., incentives, subsidies, carbon tax) could be one solution among others (hypothesis) to boost and foster the industry. The overall objective is to develop a policy analysis framework that uses a set of process system engineering tools including process analysis, process simulation, life cycle assessment (LCA), techno-economic analysis (TEA) and multi-criteria decision-making (AMCD) to 1) assess viability of biorefinery strategies; and 2) examine to what extent do policy instruments can influence strategic decision planning at an enterprise or a company level such as a pulp and paper mill. The methodology has two phases including Phase I and Phase II. In Phase I, a 3-step approach is developed. First, a set of biorefinery strategies (i.e., combination of processes/products) that has a market potential is defined. Second, the environmental and economic performances of the strategies are assessed using life cycle analysis and techno-economic analysis modelling platforms. Third, a set of decision criteria is developed to rank and select preferred strategies. The resulting outcomes from Phase I serve as a basis to assess the implication of policy instruments in Phase II. In fact, Phase II is a 3-step approach. First, based on a review, policy instruments supporting the bioeconomy are selected and used as an input into the analysis framework. Second, the potential impacts of these policy instruments on the implementation of the selected biorefinery strategies are evaluated using the embedded TEA, LCA and policy analysis-modelling platform. Third, using the decision-making matrix and criteria weights the biorefinery strategies are ranked again, and this ranking is compared with the ranking obtained in Phase I. As such, the preferences under policy instruments are compared with the preferences of decision makers under baseline conditions (no policy consideration). The methodology has been applied to a concrete case study mill. Policy instruments have been incorporated as inputs into the policy analysis framework to evaluate the decision regarding the selection of preferred forest biorefinery strategies. At first glance, the expectation was that (from mill experts): if the biorefinery projects were subsidized with government policy instruments, high capital-intensive projects would have better performance than low capital-intensive projects. Unfortunately, even with a 50% subsidy in capital cost reduction, the highest capitalintensive project didn't perform better than those having low capital-intensive. This means that the diversification of revenue streams is also an important component in the economic performance of biorefinery projects. Thus, capital-intensive projects should not rely on capital costs subsidies only, but should also develop innovative approaches and ways to target and enter low-volume and high-value market segments. However, when policy instruments are combined as policy scenarios, the profitability (IRR) of all strategies is doubled compared to the base case (with no policy consideration). The model that incorporates policy scenarios into the decision-making model (weighting matrix model) shows the extent to which the overall score and ranking of preferred biorefinery strategies could change under certain policy scenarios. As a matter of fact, the highest capital-intensive biorefinery strategy, which ranked as the least preferred among the biorefinery strategies (rejected), becomes the second most preferred strategy (ranked as number two) under certain policy scenarios. Finally, the analysis showed that governments could foster the development of bioproducts and the bioeconomy through various supports including financial programs and incentives. Government support may act as a lever for the bioeconomy and new market segment development (validation of the hypothesis). These results of this work will have a direct application in the forest industry sector and will help forest companies understand the subtle competitive aspect of nonfinancial attributes in bioeconomy especially under product environmental declaration (EPD). Thus, carbon footprint and future global carbon pricing, social perceptions are key elements and (for now) nonfinancial attributes that need to be considered by companies in order to remain competitive and attractive especially under North American Free Trade Agreement (NAFTA), Trans-Pacific Partnership (TPP) agreement, and more recently under Canada-European Union Comprehensive Economic and Trade Agreement (CETA). Using a planning approach such as the one proposed in this thesis, forest companies (1) will be able to foresee changes in the regulatory environment rather than only reacting to those changes afterward, and (2) will be better prepared and well equipped to act strategically in response to government regulatory and policy announcements.


identifier: Hashemi Doulabi, S. H. (2017). Decomposition-Based Integer Programming, Stochastic Programming, and Robust Optimization Methods for Healthcare Planning, Scheduling, and Routing Problems  [Thèse de doctorat, École Polytechnique de Montréal].

type:
Mémoire ou thèse
NonPeerReviewed

abstract: RÉSUMÉ: Il existe de nombreuses applications de planification, d'ordonnancement et de confection de tournées dans les systèmes de santé. La résolution efficace de ces problèmes peut aider les responsables de la santé à fournir des services de meilleure qualité, en utilisant efficacement les ressources médicales disponibles. En raison de la nature combinatoire de ces problèmes, dans de nombreux cas, les algorithmes de programmation en nombres entiers standards dans les logiciels commerciaux de programmation mathématique tels que CPLEX et Gurobi ne peuvent pas résoudre efficacement les modèles correspondants. Dans cette thèse, nous étudions trois problèmes de planification, d'ordonnancement et de confection de tournées des soins de santé et proposons des approches à base de décomposition utilisant la programmation en nombres entiers, la programmation stochastique et une méthode d'optimisation robuste. Le premier article de cette thèse présente un problème intégré de planification et d'ordonnancement dans le cadre des salles d'opération. Cette situation implique d'optimiser l'ordonnancement et l'affectation des chirurgies aux différentes salles d'opération, sur un horizon de planification à court terme. Nous avons pris en compte les heures de travail quotidiennes maximales des chirurgiens, le temps de nettoyage obligatoire alloué lors du passage de cas infectieux à des cas non infectieux et le respect des dates limites des chirurgies. Nous avons aussi empêché le chevauchement des chirurgies effectuées par le même chirurgien. Nous avons formulé le problème en utilisant un modèle de programmation mathématique et développé un algorithme «branch-and-price-and-cut» basé sur un modèle de programmation par contraintes pour le sous-problème. Nous avons mis en place des règles de dominance et un algorithme de détection d'infaillibilité rapide. Cet algorithme, basé sur le problème du sac à dos multidimensionnel, nous permet d'améliorer l'efficacité du modèle de programmation de contraintes. Les résultats montrent que notre méthode présente un écart à l'optimum moyen de 2,81%, ce qui surpasse de manière significative la formulation mathématique compacte dans la littérature. Dans la deuxième partie de cette thèse, pour la première fois, nous avons étudié l'optimisation des problèmes de tournées de véhicules avec visites synchronisées (VRPS) en tenant compte de stochasticité des temps de déplacement et de service. En plus d'envisager un problème d'ordonnancement des soins de santé à domicile, nous introduisons un problème d'ordonnancement des salles d'opération avec des durées stochastiques qui est une nouvelle application de VRPS. Nous avons modélisé les VRPS qui ont des durées stochastiques en programmation stochastique à deux niveaux avec des variables entières dans les deux niveaux. L'avantage du modèle proposé est que, contrairement aux modèles déterministes de la littérature VRPS, il n'a pas de contraintes «big-M». Cet avantage entraine en contrepartie la présence d'un grand nombre de variables entières dans le second niveau. Nous avons prouvé que les contraintes d'intégralité sur les variables du deuxième niveau sont triviales ce qui nous permet d'appliquer l'algorithme «L-shaped» et son implémentation branch-and-and-cut pour résoudre le problème. Nous avons amélioré le modèle en développant des inégalités valides et une fonction de bornes inférieures. Nous avons analysé les sous-problèmes de l'algorithme en L et nous avons proposé une méthode de résolution qui est beaucoup plus rapide que les algorithmes de programmation linéaire standards. En outre, nous avons étendu notre modèle pour modéliser les VRPS avec des temps de déplacement et de service dépendant du temps. Les résultats de l'optimisation montrent que, pour le problème stochastique de soins à domicile, l'algorithme «branch-and-cut» résout à l'optimalité les exemplaires avec 15 patients et 10% à 30% de visites synchronisées. Il trouve également des solutions avec un écart à l'optimum moyen de de 3,57% pour les cas avec 20 patients. De plus l'algorithme «branch-and-cut» résout à l'optimalité les problèmes d'ordonnancement stochastique des salles d'opération avec 20 chirurgies. Ceci est une amélioration considérable par rapport à la littérature qui fait état de cas avec 11 chirurgies. En outre, la modélisation proposée pour le problème dépendant du temps trouve des solutions optimales pour d'une grande portion des exemplaires d'ordonnancement de soins de santé à domicile avec 30 à 60 patients et différents taux de visites synchronisées. Dans la dernière partie de cette thèse, nous avons étudié une catégorie de modèles d'optimisation robuste en deux étapes avec des variables entières du problème adversaire. Nous avons analysé l'importance de cette classe de problèmes lors de la modélisation à deux niveaux de problèmes de planification de ressources robuste en deux étapes où certaines tâches ont des temps d'arrivée et des durées incertains. Nous considérons un problème de répartition et d'affectation d'infirmières comme une application de cette classe de modèles robustes. Nous avons appliqué la décomposition de Dantzig-Wolfe pour exploiter la structure de ces modèles, ce qui nous a permis de montrer que le problème initial se réduit à un problème robuste à une seule étape. Nous avons proposé un algorithme Benders pour le problème reformulé. Étant donné que le problème principal et le sous-problème dans l'algorithme Benders sont des programmes à nombres entiers mixtes, il requiert une quantité de calcul importante à chaque itération de l'algorithme pour les résoudre de manière optimale. Par conséquent, nous avons développé de nouvelles conditions d'arrêt pour ces programmes à nombres entiers mixtes et fourni des preuves de convergence. Nous avons développé également un algorithme heuristique appelé «dual algorithm». Dans cette heuristique, nous dualisons la relaxation linéaire du problème adversaire dans le problème reformulé et générons des coupes itérativement pour façonner l'enveloppe convexe de l'ensemble d'incertitude. Nous avons combiné cette heuristique avec l'algorithme Benders pour créer un algorithme plus efficace appelé algorithme «Benders-dual algorithm». De nombreuses expériences de calcul sur le problème de répartition et d'affectation d'infirmières sont effectuées pour comparer ces algorithmes.  ABSTRACT: There are many applications of planning, scheduling, and routing problems in healthcare systems. Efficiently solving these problems can help healthcare managers provide higher-quality services by making efficient use of available medical resources. Because of the combinatorial nature of these problems, in many cases, standard integer programming algorithms in commercial mathematical programming software such as CPLEX and Gurobi cannot solve the corresponding models effectively. In this dissertation, we study three healthcare planning, scheduling, and routing problems and propose decomposition-based integer programming, stochastic programming, and robust optimization methods for them. In the first essay of this dissertation, we study an integrated operating room planning and scheduling problem that combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature. As the second essay of this dissertation, for the first time, we study vehicle routing problems with synchronized visits (VRPS) and stochastic/time-dependent travel and service times. In addition to considering a home-health care scheduling problem, we introduce an operating room scheduling problem with stochastic durations as a novel application of VRPS. We formulate VRPS with stochastic times as a two-stage stochastic programming model with integer variables in both stages. An advantage of the proposed model is that, in contrast to the deterministic models in the VRPS literature, it does not have any big-M constraints. This advantage comes at the cost of a large number of second-stage integer variables. We prove that the integrality constraints on second-stage variables are trivial, and therefore we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem.  We enhance the model by developing valid inequalities and a lower bounding functional. We analyze the subproblems of the L-shaped algorithm and devise a solution method for them that is much faster than standard linear programming algorithms. Moreover, we extend our model to formulate VRPS with time-dependent travel and service times. Computational results show that, in the stochastic home-health care scheduling problem, the branch-and-cut algorithm optimally solves instances with 15 patients and 10% to 30% of synchronized visits. It also finds solutions with an average optimality gap of 3.57% for instances with 20 patients. Furthermore, the branch-and-cut algorithm ptimally solves stochastic operating room scheduling problems with 20 surgeries, a considerable improvement over the literature that reports on instances with 11 surgeries. In addition, the proposed formulation for the time-dependent problem solves a large portion of home-health care scheduling instances with 30 to 60 patients and different rates of synchronized visits to optimality. For the last essay of this dissertation, we also study a class of two-stage robust optimization models with integer adversarial variables. We discuss the importance of this class of problems in modeling two-stage robust resource planning problems where some tasks have uncertain arrival times and duration periods. We consider a two-stage nurse planning problem as an application of this class of robust models. We apply Dantzig-Wolfe decomposition to exploit the structure of these models and show that the original problem reduces to a singlestage robust problem. We propose a Benders algorithm for the reformulated single-stage problem. Since the master problem and subproblem in the Benders algorithm are mixed integer programs, it is computationally demanding to solve them optimally at each iteration of the algorithm. Therefore, we develop novel stopping conditions for these mixed integer programs and provide the relevant convergence proofs. We also develop a heuristic algorithm called dual algorithm. In this heuristic, we dualize the linear programming relaxation of the adversarial problem in the reformulated problem and iteratively generate cuts to shape the convex hull of the uncertainty set. We combine this heuristic with the Benders algorithm to create a more effective algorithm called Benders-dual algorithm. Extensive computational experiments on the nurse planning problem are performed to compare these algorithms.


identifier: Deck-Léger, Z.-L. (2017). Scattering in Space-Time Abruptly Modulated Structures  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse propose une contribution originale à l'étude de la propagation d'ondes électromagnétiques dans des structures modulées spatio-temporellement. Les structures modulées ont été abondamment étudiées, d'abord pour les circuits radio-fréquences et par la suite en optique, et il existe aujourd'hui plusieurs dispositifs modulés pour diverses applications. Habituellement, ces structures sont modulées avec une onde ayant une vitesse de modulation sousluminale. Dans ce travail, on s'attarde plutôt à étudier des structures dont la vitesse de modulation est superluminale. Ces structures superluminales ne contredisent pas la théorie de la relativité restreinte, car la modulation est transverse à la direction de propagation de l'onde. Ces structures ont été très peu étudiées, et elles présentent pourtant des propriétés fondamentales très intéressantes, qui seront l'objet principal de ce mémoire. Dans une première partie, on présente une méthode diagrammatique pour résoudre des structures modulées, ou spatio-temporelles (ST). On représente des structures ST dans le diagramme de Minkowski et dans le diagramme de dispersion avec les transformations de Lorentz. Dans la seconde partie, on s'attarde à résoudre un bloc superluminal, en calculant les propriétés des ondes transmises et réfléchies. En comparant les résultats obtenus avec ceux d'un bloc sousluminal, on constate que les solutions sont symétriques. Les fréquences, les angles de déflection et les amplitudes sont symétriques pour des vitesses opposées. Dans la troisième partie, une succession périodique de blocs superluminaux, qu'on nomme cristal superluminal, est étudié. On propose une méthode pour calculer les ondes transmises et réfléchies pour un cristal de durée finie. On détermine les conditions d'interférence pour une période dans un cristal. Cela nous permet de déduire les zones d'instabilités. Les résultats sont validés numériquement par la méthode des différences finies dans le domaine du temps, mieux connue sous l'acronyme anglais FDTD. Finalement, deux structures périodiques modulées sont présentées ; la première structure est un cristal sousluminal qui compresse une onde après une réflexion. La deuxième structure est un cristal stationnaire terminé par un mur en mouvement. Il est connu que l'effet Doppler inverse a lieu dans cette structure, et nous utilisons notre méthode diagrammatique pour le montrer.  ABSTRACT: In this thesis, we explore the scattering of electromagnetic waves from Space-Time Modulated (STM) structures, and provide a general method to represent and solve such structures. First, we present a diagrammatic method used throughout the thesis to solve STM structures. This diagrammatic method borrows tools from special relativity; the Minkowski diagram and Lorentz transformations. We solve four half-space modulation problems, corresponding to spatial, subluminal, temporal and superluminal modulations. Next a superluminal slab is solved diagrammatically and mathematically. A symmetry between waves scattered from subluminal and superluminal problems is uncovered. Third, we solve a succession of superluminal slabs, which we refer to as superluminal crystals. We use a method radically different from the standard Bloch-Floquet approach: the fields scattered from one slab are the incident waves for the next slab, therefore the results of each interface are cascaded. This method would not be applicable to subluminal crystals, because in that case there are multiple reflections in each slab. For superluminal crystals, there are no such reflections, and so the problem is actually simpler than the subluminal counterpart. Finally, we present two more periodic STM structures. The first is a subluminal crystal that is shown to compress waves after reflection. The second is a stationary crystal bounded by a moving wall that is known to give rise to the inverse Doppler effect. The inverse Doppler effect is explained diagrammatically, to provide additional insight.


identifier: Haidar-Ahmad, L. (2017). Extraction d'axiomes et de règles logiques à partir de définitions de wikipédia en langage naturel  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le Web sémantique repose sur la création de bases de connaissances complexes reliant les données du Web. Notamment, la base de connaissance DBpedia a été créée et est considérée aujourd'hui comme le « noyau du réseau Linked Open Data ». Cependant DBpedia repose sur une ontologie très peu riche en définitions de concepts et ne prend pas en compte l'information textuelle de Wikipedia. L'ontologie de DBpedia contient principalement des liens taxonomiques et des informations sur les instances. L'objectif de notre recherche est d'interpréter le texte en langue naturelle de Wikipédia, afin d'enrichir DBpedia avec des définitions de classes, une hiérarchie de classes (relations taxonomiques) plus riche et de nouvelles informations sur les instances. Pour ce faire, nous avons recours à une approche basée sur des patrons syntaxiques implémentés sous forme de requêtes SPARQL. Ces patrons sont exécutés sur des graphes RDF représentant l'analyse syntaxique des définitions textuelles extraites de Wikipédia. Ce travail a résulté en la création de AXIOpedia, une base de connaissances expressive contenant des axiomes complexes définissant les classes, et des triplets rdf:type reliant les instances à leurs classes.  ABSTRACT: The Semantic Web relies on the creation of rich knowledge bases which links data on the Web. In that matter, DBpedia started as a community effort and is considered today as the central interlinking hub for the emerging Web of data. However, DBpedia relies on a lighweight ontology and deals with some substantial limitations and lacks some important information that could be found in the text and the unstructured data of Wikipedia. Furthermore, the DBpedia ontology contains mainly taxonomical links and data about the instances, and lacks class definitions. The objective of this work is to enrich DBpedia with class definitions and taxonomical links using text in natural language. For this purpose, we rely on a pattern-based approach that transforms textual definitions from Wikipedia into RDF graphs, which are processed to query syntactical pattern occurrences using SPARQL. This work resulted in the creation of AXIOpedia, a rich knowledge base containing complex axioms defining classes and rdf:type relations relating instances with these classes.


identifier: Bonnard, C.-H. (2017). Méthodes d'évaluation du comportement des limiteurs de courant de court-circuit supraconducteurs résistifs intégrés dans des simulateurs de réseaux électriques  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les limiteurs de courants de court-circuit supraconducteurs sont des appareillages à fort potentiel pour les réseaux électriques. En effet, ils offrent une limitation efficace dès les premiers instants du court-circuit. On peut qualifier la limitation de "naturelle", c'est-à-dire qu'elle est intrinsèquement liée aux caractéristiques du matériau et ne nécessite pas de commande particulière. Afin de faciliter la conception et l'intégration des limiteurs de courant de court-circuit supraconducteurs résistifs (rSFCL) destinés aux réseaux électriques, il est nécessaire de disposer de modèles de simulation précis. Ces derniers doivent prendre en compte et simuler correctement (et le plus précisément possible) les phénomènes électriques et thermiques du rSFCL en présence de surintensités de courant, qu'il s'agisse d'un court-circuit franc ou d'un phénomène temporaire de plus faible amplitude. Il est difficile d'envisager la planification de l'intégration d'un rSFCL sans passer par des outils numériques qui permettent la simulation d'un tel dispositif dans un réseau électrique en régime transitoire. Il est alors plus facile d'appréhender et de prédire le comportement transitoire du limiteur dans des conditions de stress réalistes, qui peuvent comprendre une grande variété de surintensités, tant en durée qu'en amplitude. Néanmoins, les rSFCL sont des dispositifs fortement non-linéaires caractérisés par un couplage électrique et thermique très fort. L'implémentation d'un tel modèle dans un logiciel de simulation de type “circuits électriques” en régime transitoire présente un certain défi. Bien que des modèles de rSFCL existent déjà, des améliorations doivent être apportées pour prendre en compte i) l'ensemble des phénomènes physiques liés à la limitation (thermiques et électriques), ii) les propriétés géométriques des rubans supraconducteurs utilisés et iii) la possibilité de réaliser des études globales (impact du limiteur sur le réseau) et iv) l'influence de l'architecture du ruban en présence de phénomènes locaux (points chauds). Cette thèse se concentre donc sur le développement d'un modèle de rSFCL basé sur des rubans supraconducteurs de deuxième génération. Ce modèle est développé dans le logiciel EMTP-RV, qui est un outil utilisé par un grand nombre de compagnies d'électricité dans le monde. Le modèle proposé dans cette thèse repose sur une analogie qui fait le lien entre les phénomènes électriques et thermiques, et qui permet une modélisation entièrement basée sur des éléments de circuits électriques.  ABSTRACT: Superconducting fault current limiters (SFCL) are a promising technology for power systems, i.e. they provide efficient current limitation from the very beginning of the fault without requiring any control system. In fact, the current limiting characteristics are directly connected to the physical properties of superconducting materials. There is a need for accurate models to help designing resistive-type SFCLs (rSFCL) and planning their integration into electrical networks. Such models have to take into account the physics involved for simulating (as accurately as possible) the electrical and thermal behaviours for a wide range of fault conditions, i.e. high and low short-circuit currents that can be of various durations. It is difficult to see how the planning and integration of SFCLs can be realized without using numerical tools, especially tools that allow realizing power system transient simulations, such as EMTP-RV. In fact, such software packages support engineers in predicting the behaviour of SFCLs in realistic network conditions, which may comprise a wide variety of overcurrent or fault situations. However, rSFCLs exhibit highly non-linear behaviours with a strong coupling between thermal and electrical phenomena. The implementation of such a model in power systems simulation tools is therefore challenging. Although some models have been already developed over the years, improvements are needed to take into account i) all the phenomena linked to the current limitation (electrical and thermal), ii) geometric properties of superconducting tapes that are used in rSFCLs, and iii) the possibility to perform simulations at the system level, and iv) the influence of the tape architecture in relationship to local phenomena (hot spots). This thesis hence focuses on the development of a models for resistive-type SFCLs based on second generation high temperature superconducting coated conductors (2G HTS CCs), i.e. (RE)BCO tapes. The models are implemented in EMTP-RV, a tool that is used by many utilities around the world. However, the modeling technique can be adapted to other simulation tools as well. The model proposed in this thesis is based on an electro-thermal analogy, which allows modeling thermal effects with non-linear electrical circuit elements such as resistors and capacitors. The model has been developed with the aim of providing flexibility.


identifier: Quirion-Blais, O. (2017). Optimisation de tournées de véhicules en viabilité hivernale  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Cette thèse développe des outils mathématiques et informatiques pour améliorer les opérations de viabilité hivernale. En particulier, la confection des tournées de déneigement est traitée comme un problème de tournées sur les arcs avec plusieurs contraintes. Une métaheuristique est d'abord développée pour la confection de ces tournées. Par la suite, des modifications majeures sont apportées à cet algorithme pour tenir compte des caractéristiques spécifiques aux problèmes de tournées sur les arcs (arc routing problem) (ARP) sur des réseaux routiers réels. Finalement, un second problème combinant les tournées de déneigement et d'épandage avec la mise en commun de certains véhicules pour les opérations est traité. La solution développée permet de tirer parti des caractéristiques de chaque véhicule. Tout au long de la thèse, un accent particulier est porté sur l'utilisation des données réelles ainsi que sur le développement de méthodes pour faciliter l'importation et l'exportation de ces données. Les travaux entourant cette thèse débutent avec la confection de tournées de déneigement pour une ville au Québec, soit Dolbeau-Mistassini (DM). De nombreux problèmes ont été rencontrés avec l'utilisation d'une méthode tirée de la littérature. Parmi ceux-ci, on compte : — de nombreux demi-tours difficiles à exécuter par les véhicules ; — le faible respect des priorités accordées aux rues à l'échelle du réseau ; — de nombreux véhicules parcourent de longues distances pour se rendre dans les coins reculés du réseau ; — le déséquilibre des tâches de travail en raison des différentes vitesses d'opération des véhicules ; — le fait que la méthode ne tient pas compte des ruelles qui peuvent être traitées dans une direction ou dans l'autre en un seul passage. À la suite de nombreux ajustements manuels pour corriger les tournées obtenues, force a été de constater que des améliorations pouvaient être apportées à ce type de méthode. Les travaux concernant la première contribution de cette thèse ont donc porté sur le développement d'une méthode de création de tournées de déneigement. En raison du grand nombre de variables et de contraintes considérées dans le problème, le choix s'est porté sur une méthode heuristique. Ce type de méthode offre un bon équilibre entre le temps de traitement et la qualité des solutions obtenues. Plus précisément, le choix s'est arrêté sur une métaheuristique de type algorithme de recherche à voisinage adaptatif large (adaptive large neighborhood search) (ALNS), en raison du succès remporté récemment par ce type de méthode. Le premier article a permis de constater que l'algorithme développé permet de créer des tournées pour les véhicules de déneigement. Les contraintes suivantes sont respectées : équilibrage des tournées, couverture partielle du réseau, vitesses hétérogènes, restrictions de virages, restrictions rue/véhicule et hiérarchie du réseau. Pour la deuxième contribution de thèse, le problème a d'abord été formalisé par l'intermédiaire d'un programme linéaire en nombres entiers (mixed integer programming) (MIP). Le problème a été formulé comme un problème des k-postiers ruraux avec objectif minmax (min-max k-vehicles rural postman problem) (MM K-RPP) avec hiérarchies, pénalités sur virages, vitesses d'opération hétérogènes et tournées ouvertes sur un graphe mixte. Tel qu'anticipé, la résolution devient rapidement impossible à traiter avec un solveur commercial en utilisant seulement 20 segments de rue. Il a été décidé de poursuivre l'approfondissement de l'algorithme développé en première partie. Cette décision a été prise notamment en raison du très long temps de traitement qui réduit l'utilité du premier algorithme. Cette décision repose aussi sur le fait que visuellement, on constate que les tournées obtenues peuvent être améliorées. Dans cette optique, une collaboration a été initiée avec messieurs Fabien Lehuédé et Olivier Péton du laboratoire des sciences du numérique de Nantes (LS2N) à IMT Atlantique. Leur expertise avec la méthode ALNS a effectivement permis d'améliorer grandement les résultats obtenus. Parmi les améliorations apportées, on note une transformation du réseau permettant de tenir compte des pénalités sur virages lors du calcul des plus courts chemins. Cette transformation permet également de mieux prendre en compte les ruelles qui requièrent un seul passage dans une direction ou dans l'autre. De plus, la possibilité d'appliquer plusieurs fois un opérateur de destruction avant de passer à la construction est ajoutée. Cette contribution a également été l'occasion de développer et tester de nouveaux opérateurs de voisinage, développer une méthode de groupement des arcs et revoir et simplifier le code de la métaheuristique. L'algorithme a été appliqué à la première étude de cas ainsi qu'a deux nouvelles études de cas, Baie-Comeau (BC) et Plateau-Mont-Royal (PMR). Des tests ont également été exécutés en comparant les nouvelles tournées obtenues à des tournées conçues quelques années plus tôt ainsi qu'aux résultats obtenus par un solveur commercial. Les résultats obtenus démontrent que la méthodologie améliore les tournées conçues précédemment. Il est aussi possible de conclure que la méthode de groupage des arcs améliore la qualité des solutions obtenues et l'efficacité des nouveaux opérateurs développés varie selon le réseau utilisé. Pour la troisième contribution, nous sommes revenus sur le cas d'étude initial tel que décrit par les intervenants de la première étude de cas. Il a été dit que les charges de travail doivent être équilibrées, mais que certains véhicules doivent également épandre des fondants ou des abrasifs en plus de déneiger. Pour tenir compte de cette contrainte, certaines tournées avaient délibérément été gardées plus courtes dans les premières solutions. Pour le troisième article, il a été décidé de traiter cette problématique de front. Ce qu'il faut savoir est que certains véhicules sont équipés pour l'épandage et le déneigement alors que d'autres sont équipés pour le déneigement seulement. Lorsque les premiers traitent un segment de rue, ils exécutent les deux opérations simultanément. Lorsque les deuxièmes traitent un segment de rue, il faut planifier un second passage par les premiers véhicules pour qu'ils puissent épandre des fondants ou des abrasifs. L'algorithme développé précédemment a donc été modifié dans cette optique. En plus, la considération des contraintes de restrictions rue/véhicule a été ajoutée dans l'algorithme. Les résultats démontrent que l'algorithme permet effectivement de concevoir des tournées qui respectent les contraintes de la nouvelle étude de cas. Cet outil permet donc de tirer profit de l'interaction entre les divers types de véhicules. La contribution souligne également l'utilité d'un tel outil pour supporter l'analyse des besoins justifiant l'achat de nouveaux véhicules. En parallèle aux développements algorithmiques, des méthodes d'importation et d'exportation des données provenant des cas d'étude réels sont aussi développées. Dès le départ, il a été choisi d'utiliser des fichiers de type Shapefile comme source de données en raison de sa grande disponibilité et de la compatibilité avec les système d'information géographique (SIG). Une méthode pour passer du réseau géographique vers un réseau mathématique a donc été améliorée au cours des travaux. Alors qu'au début des travaux de la thèse, il fallait passer par un chiffrier Microsoft ExcelTM pour ensuite importer les données dans le code, à la fin, une méthode automatisée permet l'importation directe à partir des fichiers Shapefiles vers le code de la métaheuristique. Quant aux résultats obtenus, ils furent obtenus dans les premières étapes sous forment de représentations géographiques dans un SIG ainsi que des feuilles d'instructions indiquant les étapes, coin de rue par coin de rue, aux opérateurs de véhicules. De ce côté, les développements ont permis d'obtenir des fichiers de type KML. Ce type de fichier est compatible avec plusieurs logiciels et applications, dont Google EarthviewTM et des applications de guidage routier sur des appareils mobiles.  ABSTRACT: In this thesis, we develop mathematical and computerized tools to improve winter viability operations. More precisely, the snow routing design problem is treated as an problème de tournée sur les arcs (arc routing problem) (ARP). In a first effort to solve the problem, a metaheuristic procedure is designed. Then, some major modifications are made to the algorithm to improve the consideration of specific characteristics of real road networks. Finally, a second problem combining the routing of the snowplow and the spreading vehicles are addressed. The objective is to fully take advantage of the characteristics of the different type of vehicles. In parallel with the algorithmic development, this thesis also develops some methodologies to facilitate the importation and exportation of the real world data. Works concerning this thesis were initiated with a mandate to design snowplow routes for a city in the province of Québec, namely DM. The problem was addressed by using a methodology found in the literature, however, several difficulties were encountered. Among others: — the routes contained several U-turns which are difficult to perform by the snow plowing vehicles; — little consideration of the priorities at the network level; — several vehicles have to travel to some remote streets in the same sector of the city where we would expect only one vehicle to go; — unbalanced sectors due to the different speeds of operation of the vehicles; — no consideration for back alleys that needs to be serviced only once in either direction. In respond to these problems, several manual modifications of the routes were undertaken to make them feasible. It was found that the methodology fails to solve the problem as it is encountered. Therefore, works concerning the first contribution of this thesis focused on the development of a methodology to design snowplow routing. Due to numerous variables and constraints, it was decided to develop a metaheuristic algorithm. This type of methodology offers a good balance between runtime and the quality of the solution obtained. In particular, an ALNS is selected because of its recent success cited in the literature. Thus, the first article concludes that the algorithm can design snowplow routing. The following constraints are considered: workload balance, partial area coverage, heterogeneous vehicle speeds, road/vehicle dependencies, network hierarchies and turn restrictions. In the second contribution of this thesis, the problem was modeled as a mixed integer program. It is formulated as a min-max k-rural postmen problem with hierarchies, turn penalties, open tours and heterogeneous speed on a mixed graph. As expected, the formulation is intractable even for a number of arcs as low as 20. It was then decided to pursue the development of the ALNS algorithm. This decision was taken considering the long runtime of the first algorithm and the fact that the routes obtained can be visually improved. A collaboration with Fabien Lehuédé and Olivier Péton from the Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique was undertaken. Their expertise with ALNS greatly helped to improve the results obtained. Among other improvements brought to the algorithm, one can cite the transformation of the graph which allows to better take into account turn penalties during the computation of the shortest paths. This transformation also allows to better take into account the back alleys which only need one service in either direction. This contribution also allowed to develop and test new neighborhood operators and an arc grouping methodology. Both of these innovations improve the quality of the solutions obtained. However the efficiency of the new operators varies with the network. For the third contribution, we took back the case study as it was described by the collaborator in DM. It was said that the workload needs to be balanced among the vehicles. However some vehicles must also perform winter spreading in addition to plowing. For the first set of routes produced, some of the routes were deliberately left with a lower workload to allow them to perform winter spreading. For the third article, it was decided to consider the spreading and the plowing directly during the construction and the improvement steps. Thus this problem was tackled more directly in the third article. It must be noted that some vehicles are equipped to perform both winter spreading and snow plowing and some others can only perform plowing. When the former service a street, they can perform both plowing and spreading at the same time. When the latter service a street, a second passage is required to spread salt or abrasives. The algorithm developed for the second contribution was then adapted for this new problem. Moreover, the street/vehicle restriction constraints were also added. The result shows that the algorithm can produce a set of routes respecting the constraints of the new problem. It can take advantage of the interaction between the various types of vehicles. The article also shows that such tool can be beneficial in analyzing the requirements for new vehicles. In parallel with the development of the algorithms, data importation and exportation techniques from real road networks are also developed. It was chosen to use Shapefiles because of its good relative availability and because of its compatibility with Geographic Information System (GIS). A method to transfer from a geographical to a mathematical network is improved during the thesis. At the beginning, a Microsoft ExcelTM datasheet is used to transfer the data from the GIS to the metaheuristic. At the end, it is possible to fetch the data directly from the Shapefiles to the metaheuristic. As for the results obtained, at the beginning, they were provided in the form of a Shapefile for visualization and indications on sheets of paper for the operators. At the end, the results can be exported to the KML format. This type of file is compatible with several software such as Google EarthviewTM and application Global Positioning System (GPS) applications on mobile devices.


identifier: Dupeuble, G. (2017). Préservation de l'opacité par raffinement de systèmes spécifiés par des chaînes de Markov discrètes à intervalles  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les méthodes formelles permettent de modéliser et concevoir des systèmes informatiques critiques, notamment dans les domaines à fort risque humain que sont les transports de personne ou les centrales énergétiques, par exemple. L'une des méthodes de conception est celle dite de raffinements successifs, étapes lors desquelles les spécifications du système sont ajustées afin que le produit final soit le plus conforme possible aux exigences initiales. Le principe du raffinement est tel qu'il ne doit pas être destructif : le modèle raffiné doit vérifier au moins les mêmes requis déjà validés par le modèle précédent - par exemple, l'absence de blocage, ou la terminaison du programme dans un état acceptant.  Parmi ces requis, le système doit parfois valider des requis non-fonctionnels, tels que des propriétés de sécurité. Notamment, on se penche davantage sur la propriété d'opacité libérale. Pour modéliser les systèmes informatiques ainsi que de tels requis non-fonctionnels, on a besoin de méthodes quantitatives. Ainsi, nous choisissons comme cadre théorique le modèle de la IDTMC. Ce modèle a pour intérêt d'avoir un aspect non-déterministe. En réalité, c'est une extension du modèle de PTS : en ce sens, on considère qu'une IDTMC représente une spécification, que l'on peut implémenter par un PTS. Les PTS eux-mêmes sont des modèles probabilistes, qui permettent la mesure de propriétés quantitatives. Le second avantage de ce type de modèle est l'existence de trois types de raffinement : fort, faible et complet.  La problématique principale liée au raffinement de systèmes sécurisés est la suivante : le fait qu'une spécification vérifie une propriété de sécurité donnée n'est pas une condition nécessaire au fait que son raffinement la vérifie également. Le but est donc de trouver, dans notre cadre théorique, une notion de raffinement qui préserve la propriété de sécurité que l'on étudie. L'opacité est une propriété de sécurité introduite avec le modèle du LTS, puis étendue aux PTS : elle traduit la capacité d'un observateur extérieur à déduire l'état d'un prédicat secret en observant uniquement la partie publique des exécutions du programme. Sa première définition est une définition binaire ; en étendant la notion aux PTS, on introduit un aspect probabiliste en définissant l'opacité libérale, qui mesure la non-opacité du système, et l'opacité restrictive, qui mesure son opacité effective. Il est alors possible d'étendre à nouveau ces notions aux IDTMC : il suffit de calculer l'opacité dans le pire des cas pour l'ensemble des implémentations des IDTMC.  Ainsi, nous prouvons les résultats suivants. Tout d'abord, on prouve que l'opacité libérale dans une IDTMC non-modale, c'est-à-dire complètement définie, se calcule en un temps fini, doublement exponentiel. Nous proposons un algorithme de calcul. De plus, on prouve qu'il est possible d'approcher l'opacité libérale dans une IDTMC dans le cas général, en un temps doublement exponentiel également. Nous proposons comme contribution originale une extension de l'algorithme de calcul du cas non-modal, et nous prouvons sa correction. Enfin, on prouve que l'opacité libérale dans une spécification est préservée après raffinement faible, ce qui généralise un résultat similaire mais qui ne considérait que le raffinement fort.  En définitive, nous réalisons une preuve de concept destinée à être reproduite pour d'autres modèles et propriétés de sécurité similaires, telles que les Propriétés Rationnelles de Flux d'Information (RIFP) dont est issue l'opacité.  ABSTRACT: Formal methods can help to design any computer system - softwares, protocols, architectures, etc. Indeed, developping a system usually consists in refining it. The refined system is then a more precise one, with some more features. Thus, all these stages lead to a final product which is a working implementation of the initial specification. The key issue is as follows: each refined system must at least verify all the properties verified by the previous one. This must be the case for behaviour properties (like the absence of any deadlock) and for security properties. This issue is relatively easily resolved when it is about usual behaviour properties, but security is trickier to model. Therefore, one cannot ensure the fact that a refined system verifies the same security properties as the previous system.  This essay aims to highlight a particular security property, opacity, for which we prove that it is preserved when a system is refined. Opacity is linked to the probability for a passive external observer to know the content of a secret, only by observing the public outputs of the system. The framework is as follows. In order to modelize our specifications, we define the Interval Discrete-Time Markov Chain (IDTMC), which is a generalisation of the Probabilistic Transition System (PTS).  The probabilistic aspect is a way to introduce quantitative measurement on our models. Since IDTMC are non-deterministic, they carry a higher layer of abstraction than the PTS model. On this framework, one can define three types of refinement: strong, weak and thorough.  Since opacity is already defined on PTSs, we define its extension to IDTMC. Particularly, one can differentiate liberal opacity (the measure of non-opacity) from restrictive opacity (the measure of effective opacity). The extension is directly defined by stating the fact that the opacity of a secret in a IDTMC is the worst case among all the PTSs that implement this specification.  Then we prove the following theorems. First, if we consider a non-modal IDTMC, i.e. a specification for which each transition has a non-zero probability, then the liberal opacity of any secret is computable in 2EXP-time. We provide an algorithm to compute this value. Then, for the general case, we prove that the liberal opacity can be approximate in 2EXP-time. This original contribution comes with an extension of the previous algorithm, for which we prove its correctness. Finally, we solve the main issue of this essay: liberal opacity in a specification is preserved when the system is weakly refined. This contribution expands a similar result, which only considered strong refinement.  These results lead to a proof of concept for the fact that secured systems can be refined and keep their security properties, for a certain type of properties. This can be especially generalised to all Rational Information Flow Properties (RIFP).


identifier: André, H. (2017). Estimation de trafic routier par filtre de Kalman d'ensemble sous contrainte de confidentialité différentielle  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le but de cette recherche est de proposer un algorithme numérique pour la publication en temps réel de certaines statistiques calculées à partir de données sensibles fournies par des utilisateurs. Afin de contrôler le gain possible d'information divulguée par ces statistiques sur les utilisateurs contributeurs, nous souhaitons que notre algorithme garantisse leur confidentialité différentielle, qui est une notion forte et formelle de la confidentialité. La confidentialité différentielle stipule que le gain d'information sur la participation d'un utilisateur individuel apporté par rapport à une connaissance préalable par la publication de données est borné. Cela signifie qu'il est impossible de savoir avec beaucoup de certitude si un utilisateur donné a participé à l'élaboration des données publiées, et cela pour tout utilisateur. L'anonymat des utilisateurs est donc garanti. Assurer un niveau de confidentialité différentielle se traduit généralement en dégradant les données, de manière maîtrisée. Le but de cette recherche est donc de proposer des mécanismes assurant la confidentialité différentielle et dégradant le moins possible les données. Nous supposons qu'un modèle dynamique stochastique expliquant la génération du jeu de données est disponible et à la disposition de tous, et nous cherchons à utiliser ses caractéristiques pour améliorer la qualité des données publiées. Nous appliquons l'estimateur développé à la problématique de l'estimation de trafic routier. Les usagers de la route envoient leurs données en franchissant des capteurs statiques sur la route ou en fournissant leurs traces GPS. Un mécanisme différentiellement privé publie l'état du trafic sous la forme d'une carte spatio-temporelle de densité. Ici la confidentialité différentielle garantit que l'étude de la carte publiée au cours du temps ne peut pas révéler des informations sensibles trop précises sur les trajets des utilisateurs de la route. Les mécanismes différentiellement confidentiels sont élaborés à base de filtres : filtre de Kalman étendu, filtre de Kalman d'ensemble, filtre à particules. Nous utilisons des jeux de données synthétiques et une certaine métrique pour comparer les différents filtres entre eux. Ensuite nous testons notre estimateur différentiellement confidentiel sur un jeu de données réelles, provenant du projet Mobile Century. Cette recherche a permis de proposer un mécanisme différentiellement confidentiel à base de filtre de Kalman d'ensemble pour l'estimation de trafic routier. De plus, le fait que cet algorithme garantisse également la confidentialité différentielle avec des mesures provenant de traces GPS permet d'étendre le champs d'application à un réseau routier beaucoup plus large puisque nous ne nous restreignons plus aux routes équipées de capteurs fixes.  ABSTRACT: Road traffic estimation systems can rely nowadays on an increasing number and variety of sensors and data sources to provide better coverage and accuracy, from standard static detectors to, more recently, location traces obtained possibly from individual drivers' smartphones. Motivated by privacy concerns raised by such systems, this thesis discusses a methodology for estimating the macroscopic traffic state (density, velocity) along a road segment in real-time, while providing formal differential privacy guarantees to the individual drivers, a state-ofthe-art notion of privacy that protects against adversaries with arbitrary side-information. This translates to the inability for an adversary to make a better guess for the participation of a specific individual, with the use of differentially private data. Differential privacy provides formal proof that the relative information gain for the adversary, with publication of differentially private data, is bounded. Making data differentially private means randomizing in some way the data, thus making the published output less accurate. The goal of this research is to propose a numerical method to make private data differentially private for public release. Such methods are called differentially private mechanisms. The impact of the privacy constraint on estimation performance is mitigated by the use of a nonlinear model of the traffic dynamics, fused with the sensor measurements via an Ensemble Kalman Filter, a classical method for data assimilation. The differentially private mechanism is applied to a road traffic estimation problem Road users send their data when they cross static sensors (position, occupancy), and through their smartphones (position, speed). The differentially private mechanism publishes the density map that is usable by any third party app, and the privacy guarantees will follow. All the mechanisms are validated on synthetic data and tested on the Mobile Century dataset.


identifier: Hadengue, M. (2017). L'innovation inverse : vers un nouveau modèle d'innovation globale pour les entreprises  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Les grandes entreprises occidentales ne peuvent plus se limiter à leurs marchés historiques (les États-Unis, le Canada ou encore l'Europe de l'Ouest). Ces derniers, affectés par les récentes crises économiques et le manque de croissance, sont aujourd'hui saturés et ne présentent donc plus un potentiel de développement suffisant. À l'inverse, d'autres marchés sont en plein essor. Les pays émergents tels que le Brésil, la Chine ou l'Inde voient leurs classes moyennes se développer considérablement, créant ainsi de nouveaux marchés très attractifs. Conscientes de ces enjeux, un grand nombre d'entreprises occidentales se sont alors mises à innover pour ces nouveaux marchés. Les fortes contraintes locales, à savoir le besoin de produits non dispendieux répondant à des critères d'autonomie ou de durabilité élevés, et ce, sans compromis en termes de qualité, ont stimulé l'innovation. Les entreprises occidentales ont alors développé des solutions tout à fait originales et de grande valeur pour ces marchés émergents. Réalisant que les axes de valeur de ces nouveaux produits pourraient également permettre de créer des marchés ou de répondre à de nouveaux besoins dans les économies développées, ces multinationales se sont alors mises à faire de l'innovation inverse. Une innovation est dite inverse si elle est d'abord adoptée dans une économie émergente avant d'être ensuite ramenée et commercialisée dans une économie développée. L'innovation inverse étant un phénomène récent, la thèse de doctorat contribue à la compréhension et au positionnement théorique de ce nouveau modèle d'innovation. Sur le plan pratique, ce travail s'efforce d'identifier les facteurs clés du succès d'une telle stratégie. L'accent est mis sur les multinationales occidentales et plus spécifiquement sur le secteur de la santé. Une revue systématique de la littérature sur l'innovation inverse permet initialement de faire l'état de l'art et d'identifier les axes de recherche les plus pertinents pour améliorer la connaissance globale de ce nouveau phénomène (article 1). Trois des pistes de recherches établies par cette étude sont ensuite adressées dans la thèse (articles 2, 3 et 4). Une analyse quantitative et de contenu permet tout d'abord de valider que les entreprises du secteur de la santé pratiquent l'innovation inverse ainsi que l'impact de ce phénomène en termes de transferts technologiques (article 2). Une étude de cas permet ensuite d'identifier les challenges rencontrés par les entreprises qui pratiquent l'innovation inverse. Plusieurs mitigateurs de risques permettant de surmonter ou de prévenir ces challenges sont proposés (article 3). Finalement, un tout premier cadre théorique de l'innovation inverse est construit. Il permet le repositionnement du concept selon la perspective réseau de la multinationale et ouvre ainsi la voie à de nouvelles études empiriques (article 4). Pour élargir le débat, une discussion générale résume les principaux travaux de la thèse et ouvre la discussion sur le lien entre innovation inverse, innovation sociale et créativité. Une conclusion identifie finalement les principales contributions ainsi que les limites de la thèse et donne quelques recommandations pour les futures recherches dans ce domaine.  ABSTRACT: Western multinationals can no longer limit themselves to their historic markets (the United States, Canada or Western Europe). Indeed, these markets, affected by the recent economic crises and lack of growth, are today saturated and therefore no longer have sufficient development potential. Conversely, other markets are booming. The middle class of several emerging economies such as Brazil, China, and India are growing considerably, creating very attractive new markets. Aware of these issues, a large number of Western companies have then begun to innovate for these new markets. Strong local constraints, i.e. the need for low-priced products meeting high standards of autonomy or sustainability without compromising quality, have stimulated innovation. This has led western companies to develop very original and valuable solutions for these emerging markets. By realizing that the added value of these new products could also create markets or meet new demands in developed economies these multinationals started to do reverse innovation. An innovation is called reverse if it is first adopted in an emerging economy before being trickled up in a developed economy. Since reverse innovation is a recent phenomenon, the doctoral thesis contributes to the theoretical understanding and positioning of this new innovation model. In practical terms, this work aims at identifying the key factors for successful of such a strategy. The focus is on western multinationals and more specifically on the health sector. A systematic review of the literature on reverse innovation initially provides a state of the art and identifies the most relevant research focus to improve the overall knowledge of this new phenomenon (Article 1). Three of the research axis established by this study are then addressed in the thesis (Articles 2, 3 and 4). A quantitative and content analysis first allows verifying the practice of reverse innovation in the health sector industry and its impact in terms of technology transfer (Article 2). Then, using a case study, the challenges encountered by firms that practice reverse innovation are identified and risk mitigators are proposed (Article 3). At last, a very first theoretical framework of reverse innovation is built. It allows the repositioning of the concept according to the network perspective of the multinational and opens the way to new empirical studies (Article 4). In order to broaden the debate, a general discussion summarizes the main results of the thesis and opens the discussion on the link between reverse innovation, social innovation and creativity. A conclusion finally identifies the main contributions and limitations of the thesis and gives some recommendations for future research in this field.


identifier: Heshmati, V. (2017). Biobased PLA/PA11 Blends and the Incorporation of Cellulose Nanocrystal  [Thèse de doctorat, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Le mélange de polymère et la plastification sont connus comme deux stratégies majeures pour améliorer la ténacité du poly (acide lactique) (PLA). Cependant, l'étude de la combinaison de ces deux méthodes est absente de la littérature. Le mélange de PLA avec d'autres bioplastiques est une stratégie qui permet d'améliorer les propriétés mécaniques tout en conservant un aspect biomatériau. D'autre part, la plastification du PLA, a été la plus prometteuse pour améliorer la mobilité des chaînes du PLA. Cependant, le principal inconvénient de la plastification du PLA,  est la baisse du module et de la résistance à la traction par rapport au PLA pur. L'incorporation de nano-inclusions solides dans un mélange polymère-polymère est une voie bien connue pour développer des matériaux avec un bon équilibre de ténacité/rigidité. Dans cette dissertation, la morphologie et les propriétés mécaniques des mélanges PLA/Polyamide 11 (PA11) et la localisation de la nanocellulose cristalline dans le mélange sont étudiés. Dans la première partie de ce travail, une étude systématique de la tension interfaciale et du développement morphologique du PLA/PA11 est effectuée. Il a été démontré que la tension interfaciale dans les mélanges PLA/PA11 dans des conditions dynamiques mesurée par la technique du triangle de Neuman (3.2 mN/m) est nettement inférieure à celle mesurée dans des conditions statiques par la méthode de rupture du fil (5.8 mN/m) et la rétraction de fibre intégrée (5.4 mN/m). Dans des conditions de mélange dynamiques, les analyses morphologiques et thermiques indiquent sans ambiguïté que le système PLA/PA11 se comporte comme un système hautement interactif interfacialement compatibilisé. Il a été démontré que la mobilité restreinte de la chaîne de PLA est la raison principale de l'écart observé entre le comportement statique et dynamique des mélanges PLA/PA11. L'amélioration de la mobilité de la chaîne de PLA grâce à l'ajout de 5% de plastifiant PEO a entraîné une tension interfaciale significativement plus faible et même une coalescence supplémentaire supprimée sous un mélange dynamique à 30 et 40% de phase mineure. Ces résultats sont importants car ils indiquent clairement que, même si les polymères peuvent avoir des interactions interfaciales, une mobilité de chaîne suffisante est nécessaire pour que ces interactions entrent en jeu. Dans la deuxième partie de ce projet, l'impact profond de la mobilité contrôlée de la chaîne de PLA sur les propriétés mécaniques des mélanges PLA/PA11 est étudié. Il a été  démontré que l'amélioration de la ductilité du PLA améliorée suite à l'ajout d'une quantité optimale d'oxyde de polyéthylène (PEO), affecte de manière significative les propriétés mécaniques des mélanges PLA/PA11. Dans le mélange (PLA-15PEO)/PA11 50/50 vol%, une amélioration remarquable des propriétés mécaniques est observée avec des spécimens démontrant 17.5 fois la résistance aux chocs du PLA pur et 3 fois celui du PA11 pur. En outre, une amélioration exceptionnelle de l'allongement à la rupture à 275% a été enregistrée pour le même mélange, contre 5% pour le PLA et 6% pour le PLA/PA11. Les rôles critiques de la concentration de PEO, la séparation des phases de PLA/PEO, les interactions interfaciales et la cavitation interfaciale en tant que paramètres principaux contrôlant ce comportement de renforcement sont discutés en détail. Contrairement au PEO, le PEG n'a aucun effet en tant que plastifiant sur le durcissement du mélange PLA/PA11. Ceci est attribué à une séparation de phase PLA/PEG à des concentrations inférieures de PEG que pour PEO. Ces résultats sont d'une importance significative car ils indiquent clairement que la mobilité contrôlée des chaîne de PLA grâce à l'utilisation d'une concentration optimale d'un plastifiant approprié est une approche hautement efficace pour le développement de mélanges PLA/PA11 à haute performance. La troisième partie de ce travail présente, pour la première fois, la localisation thermodynamiquement stable des nanocristaux de cellulose (CNC) dans un mélange d'acide polylactique)/bio-polyamide11 (PA11) préparé avec une combinaison de dissolution du solvant, de coulée et de mélange à l'état fondu. La microscopie à force atomique (AFM) et l'analyse de rhéologie démontrent un niveau élevé de dispersion des CNC. Les CNC sont alimentés dans les mélanges à travers la préparation de mixtures PLA/CNC ou PA11/CNC par mélange à l'état fondu dans un mélangeur interne. Les particules CNC dans le mélange PLA/PA11 restent dans la phase PA11 lorsqu'elles sont ajoutées dans les mélanges à travers la mixture PA11/CNC. De manière significative, dans les systèmes ternaires dans lesquels les CNC sont introduits dans le mélange à travers la mixture PLA/CNC, les nanoparticules migrent de la phase de PLA qui est thermodynamiquement moins stable vers PA11, et ce indépendamment du fait que le PLA/PA11 forme une phase dispersée dans la matrice (PLA/PA11 70/30, 30/70 vol%) ou une morphologie co-continue (PLA/PA11 50/50 vol%). La localisation stable des CNC dans la phase PA11 est en accord avec les prédictions thermodynamiques. La morphologie de la phase dispersée n'est pratiquement pas affectée par l'addition de 3 wt% de CNC, ce qui est attribuée au niveau déjà faible de coalescence dans ces compositions. Cependant, l'addition de seulement 1 wt% de CNC au mélange co-continu PLA/PA11 50/50 vol%, avec le plus haut taux de coalescence, diminue considérablement le diamètre de la taille des pores de 13 μm à 3 μm. Il a été supposé que la relaxation retardée des domaines PA11 remplis par les CNC, est à l'origine cette réduction de coalescence. La dernière partie de ce travail rapporte le contrôle de la localisation stable des nano cristaux  de cellulose (CNC) dans la phase PLA dans les mélanges PLA/PA11. Une stratégie de traitement versatile est optimisée en combinant l'homogénéisation-lyophilisation afin de préparer une mixture PEO/CNC. La mixture PEO/CNC préparé est par la suite incorporé dans des mélanges PLA/PA11 en utilisant deux stratégies de mélange différentes. La microscopie à force atomique (AFM) démontre une dispersion individuelle de nanoéchelle de CNC avec une épaisseur de 10-20 nm dans des mélanges PEO, PLA-PEO et (PLA-PEO)/A11 qui se situent dans la même gamme de nanoparticules CNC individuelles. Les particules CNC se localisent sélectivement dans la phase PA11 dans un système classique PLA/PA11/CNC ternaire. Cependant, les analyses SEM et AFM dans cette étude montrent la localisation stable presque exclusive des particules CNC revêtues de PEO dans la phase PLA, que la mixture PEO/CNC soit prémélangé avec PLA ou PA11. Il est suggéré que les fortes interactions entre les particules de CNC et PEO combinées à la miscibilité de PLA/PEO facilitent la localisation de la CNC recouverte de PEO dans la phase PLA. La localisation de 2 wt% de CNC dans la phase PLA-PEO diminue la taille des pores du mélange co-continu de 11 à 4 μm. Cependant, lorsque la CNC est sélectivement localisée dans la phase PA11, un plus grand effet de coalescence réduite est observé. Ceci est lié à une structure de réseau CNC plus développée dans le dernier cas au même chargement CNC. Les résultats de cette partie indiquent une stratégie pour la ségrégation de la CNC en PLA. Ainsi, il est possible d'avoir un degré élevé de contrôle sur la localisation CNC dans les mélanges PLA/PA11.  ABSTRACT: Polymer blending and plasticization are known as two major strategies in poly(lactic acid) (PLA) toughening. A combination of these two methods, however, is lacking in the literature. The blending of PLA with other bio-plastics is a strategy that allows for tuning the mechanical properties while still maintains a bio-material. PLA plasticization on the other hand has shown the greatest promise in enhancing PLA chain mobility. The main drawback of PLA plasticization, however, is the drop in the modulus and tensile strength compared to neat PLA. Incorporation of solid nano-inclusions into polymer-polymer blend is a well-known pathway for engineering materials with a good toughness/stiffness balance. In this dissertation, the morphology and mechanical properties of PLA/PA11 blends and the localization of crystalline nanocellulose in the blend are studied.  In the first part of this work, a systematic study of the interfacial tension and morphology development of PLA/PA11 is reported. It is shown that the interfacial tension in PLA/PA11 blends under dynamic conditions measured by the Neuman Triangle technique (3.2 mN/m) is significantly lower than that measured under static conditions by the breaking thread (5.8 mN/m) and imbedded fiber retraction (5.4 mN/m) methods. Under dynamic mixing conditions, morphological and thermal analysis unambiguously indicate that the PLA/PA11 system is behaving as a highly interacting interfacially compatibilized system. It is shown that the limited PLA chain mobility is the main reason for the observed discrepancy between the static and dynamic behavior of PLA/PA11 blends. Enhancing the PLA chain mobility through the addition of 5% PEO plasticizer results in a significantly lower interfacial tension and even further suppressed coalescence under dynamic mixing at 30 and 40 vol% minor phase. These results are important since they clearly indicate that even if polymers may have the potential for interfacial interactions, sufficient chain mobility is necessary in order for those interactions to come into play. In the second part of this project, the profound impact of controlled PLA chain mobility on the mechanical properties of PLA/bio-PA11 blends, is studied. It is shown that enhanced PLA ductility due to the addition of an optimal amount of polyethylene oxide (PEO) significantly affects the mechanical properties of PLA/PA11 blends. In the (PLA-15PEO)/PA11 50/50 vol% blend a remarkable improvement in mechanical properties is observed with specimens demonstrating 17.5 times the impact strength of the neat PLA and 3 times that of neat PA11. Also an exceptional improvement in elongation at break at 275% is found for the same blend, as compared to 5% for the PLA and 6 % for PLA/PA11. The critical roles of PEO concentration, PLA/PEO phase separation, interfacial interactions and interfacial debonding/cavitation as the main parameters controlling this toughening behavior are discussed in detail. In contrast to PEO, PEG as a plasticizer has no effect on the toughening of PLA/PA11 blend. This is attributed to a PLA/PEG phase separation at lower PEG concentrations than for PEO. These results are of significant importance since they clearly indicate that controlled PLA chain mobility through the use of an optimal concentration of an appropriate plasticizer is a highly effective approach towards the development of high performance PLA/PA11 blends. The third part of this work presents, for the first time, the thermodynamically stable localization of cellulose nanocrystal (CNC) into poly (lactic acid)/bio-polyamide11 (PA11) blends prepared with a combination of solvent dissolution, casting and melt mixing. Atomic force microscopy (AFM) and rheology analysis demonstrate a high level of CNC dispersion using this technique. CNC is fed into the blends through prepared PLA/CNC or PA11/CNC mixtures via melt mixing in an internal mixer. CNC particles in the PLA/PA11 blend remain in the PA11 phase when they are added into the blends through the PA11/CNC mixture. Significantly, in the ternary systems in which CNCs are fed into the blend through the PLA/CNC mixture, the nanoparticles migrate from the less thermodynamically stable PLA phase toward PA11 irrespective of whether the PLA/PA11  forms a matrix/dispersed phase (PLA/PA11 70/30, 30/70 vol%) or a co-continuous morphology (PLA/PA11 50/50 vol%). The stable localization of CNC in the PA11 phase is in good agreement with thermodynamic predictions. The dispersed phase morphology is virtually unaffected by the addition of up to 3 wt% CNC which is attributed to the already low level of coalescence in these compositions. However, addition of only 1 wt% CNC to the PLA/PA11 50/50 vol% co-continuous blend, with the highest level of coalescence, dramatically diminishes the pore size diameter from 13 μm to 3 μm. It is postulated that the retarded relaxation of the CNC filled PA11 domains dominates this coalescence reduction.  The last part of this work, reports on the control of the stable localization of cellulose nanocrystal (CNC) in the PLA phase in melt processed poly (lactic acid) (PLA)/bio-polyamide11 (PA11) blends. A versatile processing strategy is optimized combining homogenization-freeze drying in order to prepare a PEO/CNC mixture. The prepared PEO/CNC mixture is then incorporated into PLA/PA11 blends in two different mixing strategies. Atomic force microscopy (AFM) demonstrates an individual nano-scale dispersion of CNCs with a thickness of 10-20 nm in PEO, PLA-PEO and (PLA-PEO)/PA11 blends which is in the same range of individual CNC nanoparticles. CNC particles selectively localize in PA11 phase in a classic PLA/PA11/CNC ternary systems. However, SEM and AFM analysis in this study show the almost exclusive stable localization of the PEO-coated CNC particles in the PLA phase whether PEO/CNC mixture is premixed with PLA or PA11. It is suggested that the strong interactions between PEO and CNC particles combined with PLA/PEO miscibility facilitate the localization of PEO-coated CNC in the PLA phase. The localization of 2 wt% CNC in the PLA-PEO phase diminishes the pore size of the co-continuous blend from 11 to 4 μm. However, when CNC is selectively localized in the PA11 phase a more than double effect of reduced coalescence is observed. This is related to a more highly developed CNC network structure in the latter case at the same CNC loading. The results in this part indicates a strategy for the segregation of CNC into PLA. Thus, it is possible to have a high degree of control over CNC localization in PLA/PA11 blends.


identifier: Muller, É. (2017). Application de modèles de turbulence à deux équations à la résolution éléments finis d'écoulements instationnaires  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: Ce mémoire présente le développement d'un algorithme éléments-finis tout couplé et tout adaptif utilisable pour la résolution d'écoulements turbulents  instationnaires et bidimensionnels. Par « tout adaptatif » on entend qu'il sera possible en cours de calcul de faire varier le pas d'intégration temporelle, l'ordre de la méthode d'intégration temporelle, mais aussi la finesse du maillage dans le domaine de calcul. Par application de cet algorithme on est en mesure d'obtenir une efficacité de résolution accrue, comparativement à une résolution basée sur un maillage fixe et pas de temps de fixe. La résolution se fait à l'aide de l'approximation URANS et via l'usage du modèle de turbulence k-" standard. Dans le cas d'écoulements de paroi on utilisera également les variables logarithmiques pour les inconnues relatives à la turbulence, et les lois de paroi standards à 2 échelles de vitesse pour compenser les faiblesses du modèle k-" standard en proche paroi. L'ensemble de cette approche permet une résolution robuste des problèmes fluides présentés ici. La première partie du projet consiste à implémenter dans l'algorithme une méthode d'intégration temporelle linéaire et multi-pas, à ordre et pas de temps variables. Le schéma numérique retenu est celui des méthodes « Backward Differentiation Formulas » , particulièrement adaptées aux problèmes numériquement raides. L'implémentation de ce schéma numérique est vérifiée pour les ordres 1 à 4 par la méthode des solutions manufacturées, entre autres afin de retrouver les taux de convergence théoriques des différents ordres du schéma. La solution manufacturée utilisée pour cette vérification se rapproche d'un écoulement de Poiseuille. Dans un second temps on développe une application permettant de piloter la résolution de l'écoulement turbulent instationnaire, au travers du découpage du temps simulé en intervalles de temps de durée variable, chaque transition entre intervalle de temps se faisant par un remaillage du domaine de calcul et l'interpolation de la solution précédente sur le nouveau maillage. On termine en validant le nouvel algorithme sur plusieurs cas turbulents également classiques, que sont l'écoulement sur la marche de Kim et l'écoulement autour d'un cylindre carré puis circulaire. La complexité de ces cas est suffisante pour pleinement tester la robustesse de l'algorithme ici développé.  ABSTRACT: We present the development of a new algorithm dedicated to the resolution of bidimensional unsteady and turbulent flow based on the URANS approximation. The algorithm also uses the finite elements method, and a monolithic formulation, that is to say the movement, continuity, and turbulence partial derivatives equations are solved in one block, with the use of all interaction terms. But the main originality of the algorithm is its adaptive feature, both for the time and space discretization, and leading to an effective resolution. For the time discretization we have extended the application of a hp-adaptive method using the 'Backward Differentiation Formulas' (BDF), formerly designed to solve unsteady laminar in a effective way, to turbulent problems. The error estimation to adapt the time step has been modified to deal with the differencies between the velocity and turbulence variables. An adjustment of the stability indicator used to perform the order adaptation of the method has also been done for the same reason. The algorithm can adapt the space discretization as well thanks to a posteriori error estimation using a local projection method. A driver program has been created to control the frequency of the mesh update during the resolution of an unsteady problem, and to keep a number of nodes in the mesh approximatively constant during the whole simulation. All the developments and simulations use the standard k-" turbulence model to predict the effects of turbulence on the flow. To avoid transient negative values for turbulence variables, the natural logarithm of turbulence variables is used too. It has also been necessary to use a two velocity scales wall function to solve confined flows, or flows around a solid, to compensate for the weaknesses of the standard k-" turbulence model in such cases. The developed algorithm has been checked, with the method of manufactured solutions. First, the standard k-" turbulence model has been tested to verify that our implementations did not introduce bugs in the resolution of steady problems. We then looked for the theoretical convergence rates of the BDF for all solved variables. We have also verified the performance of the error estimator used for the time step adaptation. Finally we put our algorithm into practice to solve some widely studied turbulent flows, to compare our results with steady simulations or with other unsteady results found in the literature.


identifier: Raux, T. (2017). Étude de conditions limites de sortie pour la méthode des éléments finis  [Mémoire de maîtrise, École Polytechnique de Montréal].

abstract: RÉSUMÉ: La résolution numérique des équations de Navier-Stokes nécessite l'utilisation d'un domaine de calcul discrétisé. Quelque soit la méthode de détermination des champs de vitesse et de pression du fluide, l'augmentation du nombre de Reynolds implique un agrandissement indubitable de la taille du domaine. Ce qui revient à accroître la durée de la simulation ainsi que la demande en ressources informatiques. Au contraire, dans le cas où la taille du domaine de calcul est petite, les frontières influenceront l'écoulement interne et pollueront le signal et les données de la simulation. Nous présentons une famille de conditions limites diffusives de sortie utile lors de simulations numériques d'écoulements fluides incompressibles sur des domaines sévèrement tronqués. La forme générale de ces conditions limites assure la stabilité des calculs et la précision des résultats, même lorsque l'écoulement provoque des tourbillons importants et des reflux de fluide à la frontière de sortie. Le code numérique employé pour traiter ce genre de cas est basé sur un schéma implicite fortement couplé et sur la méthode des éléments spectraux. La discrétisation temporelle est bâtie sur une heuristique adaptative en pas de temps et en ordre. Ce logiciel est interne à l'École Polytechnique de Montréal et en continuel développement. Le projet de ce mémoire est de mettre en oeuvre la famille de conditions limites et d'analyser les résultats de simulations à haut nombre de Reynolds d'un écoulement autour d'un cylindre carré en repère absolu et en repère relatif en translation. Dans un premier temps, nous vérifions et validons le code complet pour ensuite optimiser le choix des valeurs des paramètres de configuration. Puis, nous introduisons la théorie énergétique derrière les conditions limites diffusives et les implémentons numériquement. Nous effectuons alors de nombreux tests en repère absolu à divers nombres de Reynolds et sur différentes longueurs de domaine afin de comparer les résultats avec des valeurs provenant de la littérature. Finalement, nous simulons le phénomène des vibrations induites par vortex (VIV) autour d'un cylindre carré à Re = 500 sur un domaine sévèrement tronqué. L'analyse poussée de l'influence des conditions limites de sortie sur un tel phénomène amène à la conclusion suivante. Quelque soit la condition limite choisie, si la longueur du domaine est trop faible, alors les mouvements longitudinaux du solide seront forcément limités. En revanche, une légère perte en précision est acceptable face aux gains en temps et en ressources obtenus par la réduction de la taille du domaine de calcul et par l'imposition de conditions limites de sortie.  ABSTRACT: When numerically analyzing the Navier-Stokes equations and the von Kármán streets, the typical approach is to compute the velocity and pressure fields on huge domains. Indeed the vortices generated by the obstacle last and dissipate only far downstream. But a vast geometry involves a mesh containing hundreds of thousands of nodes, thus resulting in both time- and resource-consuming simulations. We present a generalized form of outflow boundary conditions for simulating incompressible flows on severely truncated domains. It ensures the energy stability of the system, even when strong vortices cross the outflow boundary. Our numerical algorithm used for treating such situations is based on the spectral element method implemented implicitely. The adaptative time discretization speeds up the data processing by choosing heuristically its time step size and its order. This software is the property of the École Polytechnique de Montréal and is in continuous development. Our goal is to implement the outflow boundary conditions and to analyze the simulations of fluid flows past a square cylinder at high Renolds numbers on a short geometry. After verifying and validating the software through simple examples, we introduce the boundary conditions. We simulate incompressible fluid flows around a square cylinder to evaluate the robustness and accuracy of these conditions. Finally, we solve fluid-structure problems and study the vortex-induced vibrations (VIV) phenomenon at Re = 500 on severely truncated domains. We show that the open boundary conditions and the numerical algorithm developed herein produce stable simulations in such simulations. But the user must find a balance between savings in time and computational resources and a slight loss of precision.