Development of new scenario decomposition techniques for linear and nonlinear stochastic programming

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif.

Activation chimiosélective et dérivatisation d’amides et d'alcools : synthèse de plusieurs groupements fonctionnels et hétérocycles

Un objectif majeur en chimie organique est le développement de méthodes de synthèses générales, simples et peu coûteuses permettant la modification efficace des ressources naturelles en différents produits d’intérêt public. En particulier, la recherche de méthodes chimiosélectives et de méthodes dites « vertes » représente un intérêt croissant pour le secteur industriel (dont le domaine pharmaceutique). En fait, l’application en synthèse sur grande échelle de procédés catalytiques, sélectifs et utilisant des conditions douces permet de réduire le volume de déchets et la demande énergétique, minimisant ainsi les coûts de production et les effets néfastes sur l’environnement. Dans ce contexte, le groupe de recherche du Professeur André B. Charette de l’Université de Montréal s’intéresse au développement de méthodes générales et chimiosélectives permettant la transformation de fonctionnalités aisément accessibles tels que les amides et les alcools. La fonction amide, aussi appelée liaison peptidique dans les protéines, est présente dans diverses familles de molécules naturelles et est couramment employée comme intermédiaire synthétique dans la synthèse de produits d’intérêt pharmaceutique. Le groupement alcool est, quant à lui, l’une des fonctionnalités les plus abondantes dans la nature, intrinsèquement et largement utilisé en chimie de synthèse. Dans le cadre de cette thèse, des transformations simples, générales et chimiosélectives ont été réalisées sur des amides secondaires et tertiaires, ainsi que sur des alcools primaires et secondaires. La première partie de ce manuscrit se penche sur l’activation de la fonction amide par l’anhydride triflique (Tf2O), suivie de l’addition nucléophile de différents réactifs permettant ainsi la formation de plusieurs groupements fonctionnels versatiles, parfois indispensables, couramment employés en chimie organique tels que les aldimines, les aldéhydes, les amines, les cétones, les cétimines et des dérivés de la fonction amidrazone. Cette dernière fonctionnalité a également été utilisée dans des réactions successives vers la formation d’hétérocycles. De ce fait, des 1,2,4-triazoles ont été formés suite à une cyclodéshydratation initiée en conditions thermiques et faiblement acides. D’autre part, des 3-aminoindazoles ont été synthétisés par une fonctionnalisation C–H catalysée par un sel de palladium (II). La deuxième partie de la thèse est consacrée à la réaction de Mitsunobu en conditions acides, permettant ainsi la substitution nucléophile d’alcools en présence de carbamines (ou amines ne possédant pas de groupement électro-attracteurs). Ce type de nucléophile, basique lorsqu’utilisé comme base libre (avec un pKa se situant au-dessus de 13 dans le DMSO), n’est intrinsèquement pas compatible dans les conditions standards de la réaction de Mitsunobu. Contrairement aux conditions usuelles multi-étapes employant la réaction de Mitsunobu, la méthode développée au cours de cette étude permet la formation d’amines substituées en une seule étape et ne requiert pas l’emploi de groupements protecteurs.

Simulateur compilé d’une description multi-langage des systèmes hétérogènes

La conception de systèmes hétérogènes exige deux étapes importantes, à savoir : la modélisation et la simulation. Habituellement, des simulateurs sont reliés et synchronisés en employant un bus de co-simulation. Les approches courantes ont beaucoup d’inconvénients : elles ne sont pas toujours adaptées aux environnements distribués, le temps d’exécution de simulation peut être très décevant, et chaque simulateur a son propre noyau de simulation. Nous proposons une nouvelle approche qui consiste au développement d’un simulateur compilé multi-langage où chaque modèle peut être décrit en employant différents langages de modélisation tel que SystemC, ESyS.Net ou autres. Chaque modèle contient généralement des modules et des moyens de communications entre eux. Les modules décrivent des fonctionnalités propres à un système souhaité. Leur description est réalisée en utilisant la programmation orientée objet et peut être décrite en utilisant une syntaxe que l’utilisateur aura choisie. Nous proposons ainsi une séparation entre le langage de modélisation et la simulation. Les modèles sont transformés en une même représentation interne qui pourrait être vue comme ensemble d’objets. Notre environnement compile les objets internes en produisant un code unifié au lieu d’utiliser plusieurs langages de modélisation qui ajoutent beaucoup de mécanismes de communications et des informations supplémentaires. Les optimisations peuvent inclure différents mécanismes tels que le regroupement des processus en un seul processus séquentiel tout en respectant la sémantique des modèles. Nous utiliserons deux niveaux d’abstraction soit le « register transfer level » (RTL) et le « transaction level modeling » (TLM). Le RTL permet une modélisation à bas niveau d’abstraction et la communication entre les modules se fait à l’aide de signaux et des signalisations. Le TLM est une modélisation d’une communication transactionnelle à un plus haut niveau d’abstraction. Notre objectif est de supporter ces deux types de simulation, mais en laissant à l’usager le choix du langage de modélisation. De même, nous proposons d’utiliser un seul noyau au lieu de plusieurs et d’enlever le bus de co-simulation pour accélérer le temps de simulation.

La programmation télévisée au Québec et l’auditoire des 12-17 ans : analyse comparative de l’offre et de la consommation

Ce mémoire consiste en une analyse des stratégies de l’offre et de la demande de l’industrie québécoise de la production télévisuelle francophone pour la jeunesse et plus précisément, pour l’auditoire des 12-17 ans. Cette industrie tendrait à investir davantage dans l’importation que dans la production d’émissions pour cet auditoire, dû à la faible écoute de ses productions par leur auditoire cible. Afin de mieux saisir les enjeux politiques, économiques et sociaux qui entourent l’industrie de la production télévisuelle pour la jeunesse, nous proposons d’explorer et de comparer l’offre télévisuelle destinée aux 12-17 ans et leur consommation télévisuelle. Cette analyse quantitative et statistique de l’offre et de la consommation se fait en trois étapes : (i) l’analyse de la structure de réception (émissions à succès, écoute des filles et des garçons, temps passé à l’écoute), (ii) l’analyse de la structure de programmation (mode de diffusion, genres télévisuels, origine des émissions, thématiques des émissions), et (iii) l’analyse de la structure thématique (thématiques associées aux épisodes et des personnages). De ces analyses, divers constats apparaissent. Tout d’abord, les jeunes consomment ce que les télédiffuseurs diffusent à leur intention, malgré l’accès limité à cette offre. De plus, plusieurs tactiques semblent être mises en œuvre afin de rentabiliser la diffusion de ces émissions, principalement la rediffusion. Finalement, ces émissions destinées aux adolescents se distinguent de celles offertes au grand public, non seulement par le public qu’elles tentent de rejoindre, mais aussi par les thématiques qu’elles abordent et la manière dont elles les abordent.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

JSreal : un réalisateur de texte pour la programmation web

Site web associé au mémoire: http://daou.st/JSreal

Contribution à l’élaboration d’un guide alimentaire béninois : approche par la programmation linéaire et validation sur le terrain

Contexte: Le Bénin est atteint par le double fardeau nutritionnel : dans le même pays, et parfois dans le même ménage, il y a des personnes malnutries et d’autres aux prises avec des maladies chroniques. Ces conditions, au moins pour partie, peuvent être prévenues si la population est sensibilisée à de bonnes habitudes alimentaires. Pour ce faire, les professionnels de la santé ont besoin d’outils comme un guide alimentaire (GA) pour faciliter l’apprentissage de bonnes pratiques alimentaires. Ce dernier nécessite plusieurs étapes à son élaboration, dont la définition des groupes alimentaires, la présentation visuelle et la quantification des portions d'aliments. Objectif : Ce travail a eu pour but de proposer et d’homologuer des portions quotidiennes d’aliments dans chaque groupe alimentaire pour différents groupes d’âge de Béninois. Méthode : Elle consiste à : 1) Caractériser la consommation alimentaire locale; 2) Optimiser le profil moyen de consommation alimentaire quotidienne à l’aide de la programmation linéaire (PL); 3) Traduire les résultats en termes de nombre et taille de portions d’aliments de chaque groupe à consommer quotidiennement; 4) Illustrer les recommandations au moyen d’exemples de menus journaliers; 5) Homologuer le prototype du GA avec des experts béninois. La PL a permis de déterminer les choix d’aliments et quantités optimales à recommander à partir des enquêtes transversales récentes et des recommandations nutritionnelles de l’OMS. Résultats : Les quantités et portions d'aliments recommandées à la consommation ont été déterminées. Les résultats ont été partagés avec les personnes-ressources en nutrition au Bénin. Le premier prototype du GA a été développé pour restitution subséquente aux autorités du Bénin.

Domain/Multi-Domain Protection and Provisioning in Optical Networks

L’évolution récente des commutateurs de sélection de longueurs d’onde (WSS -Wavelength Selective Switch) favorise le développement du multiplexeur optique d’insertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) à plusieurs degrés sans orientation ni coloration, considéré comme un équipement fort prometteur pour les réseaux maillés du futur relativement au multiplexage en longueur d’onde (WDM -Wavelength Division Multiplexing ). Cependant, leur propriété de commutation asymétrique complique la question de l’acheminement et de l’attribution des longueur d’ondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette propriété d’asymétrie. L’interruption des services causée par des défauts d’équipements sur les chemins optiques (résultat provenant de la résolution du problème RWA) a pour conséquence la perte d’une grande quantité de données. Les recherches deviennent ainsi incontournables afin d’assurer la survie fonctionnelle des réseaux optiques, à savoir, le maintien des services, en particulier en cas de pannes d’équipement. La plupart des publications antérieures portaient particulièrement sur l’utilisation d’un système de protection permettant de garantir le reroutage du trafic en cas d’un défaut d’un lien. Cependant, la conception de la protection contre le défaut d’un lien ne s’avère pas toujours suffisante en termes de survie des réseaux WDM à partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris d’équipements, les pannes de deux ou trois liens, etc. En outre, il y a des défis considérables pour protéger les grands réseaux optiques multidomaines composés de réseaux associés à un domaine simple, interconnectés par des liens interdomaines, où les détails topologiques internes d’un domaine ne sont généralement pas partagés à l’extérieur. La présente thèse a pour objectif de proposer des modèles d’optimisation de grande taille et des solutions aux problèmes mentionnés ci-dessus. Ces modèles-ci permettent de générer des solutions optimales ou quasi-optimales avec des écarts d’optimalité mathématiquement prouvée. Pour ce faire, nous avons recours à la technique de génération de colonnes afin de résoudre les problèmes inhérents à la programmation linéaire de grande envergure. Concernant la question de l’approvisionnement dans les réseaux optiques, nous proposons un nouveau modèle de programmation linéaire en nombres entiers (ILP - Integer Linear Programming) au problème RWA afin de maximiser le nombre de requêtes acceptées (GoS - Grade of Service). Le modèle résultant constitue celui de l’optimisation d’un ILP de grande taille, ce qui permet d’obtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymétriques et accompagnés d’une matrice de connectivité de commutation donnée. Ensuite, nous modifions le modèle et proposons une solution au problème RWA afin de trouver la meilleure matrice de commutation pour un nombre donné de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualité d’écoulement du trafic GoS. Relativement à la protection des réseaux d’un domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous développons la protection d’un réseau d’un domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indépendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dépendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modèles de flots pour les p-cycles FDPP soumis à des pannes multiples. Le nouveau modèle soulève un problème de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes d’élimination de sous-tour. Par conséquent, afin de résoudre efficacement ce problème, on examine : (i) une décomposition hiérarchique du problème auxiliaire dans le modèle de décomposition, (ii) des heuristiques pour gérer efficacement le grand nombre de contraintes. À propos de la protection dans les réseaux multidomaines, nous proposons des systèmes de protection contre les pannes d’un lien. Tout d’abord, un modèle d’optimisation est proposé pour un système de protection centralisée, en supposant que la gestion du réseau soit au courant de tous les détails des topologies physiques des domaines. Nous proposons ensuite un modèle distribué de l’optimisation de la protection dans les réseaux optiques multidomaines, une formulation beaucoup plus réaliste car elle est basée sur l’hypothèse d’une gestion de réseau distribué. Ensuite, nous ajoutons une bande pasiv sante partagée afin de réduire le coût de la protection. Plus précisément, la bande passante de chaque lien intra-domaine est partagée entre les p-cycles FIPP et les p-cycles dans une première étude, puis entre les chemins pour lien/chemin de protection dans une deuxième étude. Enfin, nous recommandons des stratégies parallèles aux solutions de grands réseaux optiques multidomaines. Les résultats de l’étude permettent d’élaborer une conception efficace d’un système de protection pour un très large réseau multidomaine (45 domaines), le plus large examiné dans la littérature, avec un système à la fois centralisé et distribué.

A Mono- and Multi-objective Approach for Recommending Software Refactoring

Les systèmes logiciels sont devenus de plus en plus répondus et importants dans notre société. Ainsi, il y a un besoin constant de logiciels de haute qualité. Pour améliorer la qualité de logiciels, l’une des techniques les plus utilisées est le refactoring qui sert à améliorer la structure d'un programme tout en préservant son comportement externe. Le refactoring promet, s'il est appliqué convenablement, à améliorer la compréhensibilité, la maintenabilité et l'extensibilité du logiciel tout en améliorant la productivité des programmeurs. En général, le refactoring pourra s’appliquer au niveau de spécification, conception ou code. Cette thèse porte sur l'automatisation de processus de recommandation de refactoring, au niveau code, s’appliquant en deux étapes principales: 1) la détection des fragments de code qui devraient être améliorés (e.g., les défauts de conception), et 2) l'identification des solutions de refactoring à appliquer. Pour la première étape, nous traduisons des régularités qui peuvent être trouvés dans des exemples de défauts de conception. Nous utilisons un algorithme génétique pour générer automatiquement des règles de détection à partir des exemples de défauts. Pour la deuxième étape, nous introduisons une approche se basant sur une recherche heuristique. Le processus consiste à trouver la séquence optimale d'opérations de refactoring permettant d'améliorer la qualité du logiciel en minimisant le nombre de défauts tout en priorisant les instances les plus critiques. De plus, nous explorons d'autres objectifs à optimiser: le nombre de changements requis pour appliquer la solution de refactoring, la préservation de la sémantique, et la consistance avec l’historique de changements. Ainsi, réduire le nombre de changements permets de garder autant que possible avec la conception initiale. La préservation de la sémantique assure que le programme restructuré est sémantiquement cohérent. De plus, nous utilisons l'historique de changement pour suggérer de nouveaux refactorings dans des contextes similaires. En outre, nous introduisons une approche multi-objective pour améliorer les attributs de qualité du logiciel (la flexibilité, la maintenabilité, etc.), fixer les « mauvaises » pratiques de conception (défauts de conception), tout en introduisant les « bonnes » pratiques de conception (patrons de conception).

Multi-view 3D reconstruction using virtual cameras

Ce mémoire s'intéresse à la reconstruction d'un modèle 3D à partir de plusieurs images. Le modèle 3D est élaboré avec une représentation hiérarchique de voxels sous la forme d'un octree. Un cube englobant le modèle 3D est calculé à partir de la position des caméras. Ce cube contient les voxels et il définit la position de caméras virtuelles. Le modèle 3D est initialisé par une enveloppe convexe basée sur la couleur uniforme du fond des images. Cette enveloppe permet de creuser la périphérie du modèle 3D. Ensuite un coût pondéré est calculé pour évaluer la qualité de chaque voxel à faire partie de la surface de l'objet. Ce coût tient compte de la similarité des pixels provenant de chaque image associée à la caméra virtuelle. Finalement et pour chacune des caméras virtuelles, une surface est calculée basée sur le coût en utilisant la méthode de SGM. La méthode SGM tient compte du voisinage lors du calcul de profondeur et ce mémoire présente une variation de la méthode pour tenir compte des voxels précédemment exclus du modèle par l'étape d'initialisation ou de creusage par une autre surface. Par la suite, les surfaces calculées sont utilisées pour creuser et finaliser le modèle 3D. Ce mémoire présente une combinaison innovante d'étapes permettant de créer un modèle 3D basé sur un ensemble d'images existant ou encore sur une suite d'images capturées en série pouvant mener à la création d'un modèle 3D en temps réel.

International Transmission of the Business Cycle in a Multi-Sector Model.

Multi-country models have not been very successful in replicating important features of the international transmission of business cycles. Standard models predict cross-country correlations of output and consumption which are respectively too low and too high. In this paper, we build a multi-country model of the business cycle with multiple sectors in order to analyze the role of sectoral shocks in the international transmission of the business cycle. We find that a model with multiple sectors generates a higher cross-country correlation of output than standard one-sector models, and a lower cross-country correlation of consumption. In addition, it predicts cross-country correlations of employment and investment that are closer to the data than the standard model. We also analyze the relative effects of multiple sectors, trade in intermediate goods, imperfect substitution between domestic and foreign goods, home preference, capital adjustment costs, and capital depreciation on the international transmission of the business cycle.

Harsanyi’s Social Aggregation Theorem : A Multi-Profile Approach with Variable-Population Extensions

This paper provides new versions of Harsanyi’s social aggregation theorem that are formulated in terms of prospects rather than lotteries. Strengthening an earlier result, fixed-population ex-ante utilitarianism is characterized in a multi-profile setting with fixed probabilities. In addition, we extend the social aggregation theorem to social-evaluation problems under uncertainty with a variable population and generalize our approach to uncertain alternatives, which consist of compound vectors of probability distributions and prospects.

Choosing Wisely: The Natural Multi-Bidding Mechanism

Pérez-Castrillo and Wettstein (2002) propose a multi-bidding mechanism to determine a winner from a set of possible projects. The winning project is implemented and its surplus is shared among the agents. In the multi-bidding mechanism each agent announces a vector of bids, one for each possible project, that are constrained to sum up to zero. In addition, each agent chooses a favorite a object which is used as a tie-breaker if several projects receive the same highest aggregate bid. Since more desirable projects receive larger bids, it is natural to consider the multi-bidding mechanism without the announcement of favorite projects. We show that the merits of the multi-bidding mechanism appear not to be robust to this natural simplification. Specifically, a Nash equilibrium exists if and only if there are at least two individually optimal projects and all individually optimal projects are efficient.

The Transmission of Monetary Policy in a Multi-Sector Economy

This paper constructs and estimates a sticky-price, Dynamic Stochastic General Equilibrium model with heterogenous production sectors. Sectors differ in price stickiness, capital-adjustment costs and production technology, and use output from each other as material and investment inputs following an Input-Output Matrix and Capital Flow Table that represent the U.S. economy. By relaxing the standard assumption of symmetry, this model allows different sectoral dynamics in response to monetary policy shocks. The model is estimated by Simulated Method of Moments using sectoral and aggregate U.S. time series. Results indicate 1) substantial heterogeneity in price stickiness across sectors, with quantitatively larger differences between services and goods than previously found in micro studies that focus on final goods alone, 2) a strong sensitivity to monetary policy shocks on the part of construction and durable manufacturing, and 3) similar quantitative predictions at the aggregate level by the multi-sector model and a standard model that assumes symmetry across sectors.

Implantation de Metalib : par où commencer? Les principales étapes de l’implantation à l’université de Montréal.

Présentation des étapes d'implantation de Metalib (le répertoire de ressources électroniques Maestro) à l'Université de Montréal, lors de la Journée d’information du 8 septembre 2006 intitulée "La bibliothèque de recherche virtuelle québécoise (BRVQ) : une vision commune d’une réalisation en devenir", organisée par la CREPUQ.