L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

La recherche de naines brunes et étoiles de faible masse dans les associations cinématiques jeunes du voisinage solaire

L’objectif principal de cette thèse est d’identifier les étoiles de faible masse et naines brunes membres d’associations cinématiques jeunes du voisinage solaire. Ces associations sont typiquement âgées de moins de 200 millions d’années et regroupent chacune un ensemble d’étoiles s’étant formées au même moment et dans un même environnement. La majorité de leurs membres d'environ plus de 0.3 fois la masse du Soleil sont déjà connus, cependant les membres moins massifs (et moins brillants) nous échappent encore. Leur identification permettra de lever le voile sur plusieurs questions fondamentales en astrophysique. En particulier, le fait de cibler des objets jeunes, encore chauds et lumineux par leur formation récente, permettra d’atteindre un régime de masses encore peu exploré, jusqu'à seulement quelques fois la masse de Jupiter. Elles nous permettront entre autres de contraindre la fonction de masse initiale et d'explorer la connection entre naines brunes et exoplanètes, étant donné que les moins massives des naines brunes jeunes auront des propriétés physiques très semblables aux exoplanètes géantes gazeuses. Pour mener à bien ce projet, nous avons adapté l'outil statistique BANYAN I pour qu'il soit applicable aux objets de très faibles masses en plus de lui apporter plusieurs améliorations. Nous avons entre autres inclus l'utilisation de deux diagrammes couleur-magnitude permettant de différencier les étoiles de faible masse et naines brunes jeunes à celles plus vieilles, ajouté l'utilisation de probabilités a priori pour rendre les résultats plus réalistes, adapté les modèles spatiaux et cinématiques des associations jeunes en utilisant des ellipsoïdes gaussiennes tridimensionnelles dont l'alignement des axes est libre, effectué une analyse Monte Carlo pour caractériser le taux de faux-positifs et faux-négatifs, puis revu la structure du code informatique pour le rendre plus efficace. Dans un premier temps, nous avons utilisé ce nouvel algorithme, BANYAN II, pour identifier 25 nouvelles candidates membres d'associations jeunes parmi un échantillon de 158 étoiles de faible masse (de types spectraux > M4) et naines brunes jeunes déjà connues. Nous avons ensuite effectué la corrélation croisée de deux catalogues couvrant tout le ciel en lumière proche-infrarouge et contenant ~ 500 millions d’objets célestes pour identifier environ 100 000 candidates naines brunes et étoiles de faible masse du voisinage solaire. À l'aide de l'outil BANYAN II, nous avons alors identifié quelques centaines d'objets appartenant fort probablement à une association jeune parmi cet échantillon et effectué un suivi spectroscopique en lumière proche-infrarouge pour les caractériser. Les travaux présentés ici ont mené à l'identification de 79 candidates naines brunes jeunes ainsi que 150 candidates étoiles de faible masse jeunes, puis un suivi spectroscopique nous a permis de confirmer le jeune âge de 49 de ces naines brunes et 62 de ces étoiles de faible masse. Nous avons ainsi approximativement doublé le nombre de naines brunes jeunes connues, ce qui a ouvert la porte à une caractérisation statistique de leur population. Ces nouvelles naines brunes jeunes représentent un laboratoire idéal pour mieux comprendre l'atmosphère des exoplanètes géantes gazeuses. Nous avons identifié les premiers signes d’une remontée dans la fonction de masse initiale des naines brunes aux très faibles masses dans l'association jeune Tucana-Horologium, ce qui pourrait indiquer que l’éjection d’exoplanètes joue un rôle important dans la composition de leur population. Les résultats du suivi spectroscopique nous ont permis de construire une séquence empirique complète pour les types spectraux M5-L5 à l'âge du champ, à faible (β) et très faible (γ) gravité de surface. Nous avons effectué une comparaison de ces données aux modèles d'évolution et d'atmosphère, puis nous avons construit un ensemble de séquences empiriques de couleur-magnitude et types spectraux-magnitude pour les naines brunes jeunes. Finalement, nous avons découvert deux nouvelles exoplanètes par un suivi en imagerie directe des étoiles jeunes de faible masse identifiées dans ce projet. La future mission GAIA et le suivi spectroscopique complet des candidates présentées dans cette thèse permettront de confirmer leur appartenance aux associations jeunes et de contraindre la fonction de masse initiale dans le régime sous-stellaire.

Recherche de motifs structuraux dans les complexes acides ribonucléiques/protéines

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Recherche de motifs structuraux dans les complexes acides ribonucléiques/protéines

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Méthodes de segmentation du ventricule gauche basée sur l'algorithme graph cut pour les images par résonance magnétique et échocardiographiques

L’échocardiographie et l’imagerie par résonance magnétique sont toutes deux des techniques non invasives utilisées en clinique afin de diagnostiquer ou faire le suivi de maladies cardiaques. La première mesure un délai entre l’émission et la réception d’ultrasons traversant le corps, tandis que l’autre mesure un signal électromagnétique généré par des protons d’hydrogène présents dans le corps humain. Les résultats des acquisitions de ces deux modalités d’imagerie sont fondamentalement différents, mais contiennent dans les deux cas de l’information sur les structures du coeur humain. La segmentation du ventricule gauche consiste à délimiter les parois internes du muscle cardiaque, le myocarde, afin d’en calculer différentes métriques cliniques utiles au diagnostic et au suivi de différentes maladies cardiaques, telle la quantité de sang qui circule à chaque battement de coeur. Suite à un infarctus ou autre condition, les performances ainsi que la forme du coeur en sont affectées. L’imagerie du ventricule gauche est utilisée afin d’aider les cardiologues à poser les bons diagnostics. Cependant, dessiner les tracés manuels du ventricule gauche requiert un temps non négligeable aux cardiologues experts, d’où l’intérêt pour une méthode de segmentation automatisée fiable et rapide. Ce mémoire porte sur la segmentation du ventricule gauche. La plupart des méthodes existantes sont spécifiques à une seule modalité d’imagerie. Celle proposée dans ce document permet de traiter rapidement des acquisitions provenant de deux modalités avec une précision de segmentation équivalente au tracé manuel d’un expert. Pour y parvenir, elle opère dans un espace anatomique, induisant ainsi une forme a priori implicite. L’algorithme de Graph Cut, combiné avec des stratégies telles les cartes probabilistes et les enveloppes convexes régionales, parvient à générer des résultats qui équivalent (ou qui, pour la majorité des cas, surpassent) l’état de l’art ii Sommaire au moment de la rédaction de ce mémoire. La performance de la méthode proposée, quant à l’état de l’art, a été démontrée lors d’un concours international. Elle est également validée exhaustivement via trois bases de données complètes en se comparant aux tracés manuels de deux experts et des tracés automatisés du logiciel Syngovia. Cette recherche est un projet collaboratif avec l’Université de Bourgogne, en France.

Recensão de: CHARLOT, Bernard (1999). Le Rapport au Savoir en milieu populaire. Une recherche dans les Lycées Professionnels de banlieue. Paris: Anthropos, 390 p.

Revista Lusófona de Educação

Ethno-pragmatique et prosodie. Présentation d'une hypothèse de recherche pluridisciplinaire dans le domaine des sciences du langage et de la culture

L'hypothèse de recherche que nous souhaitons vous présenter ici a pour objet l&s fonctions pragmatiques de Ia prosodie. L'ensemble de notre Projet de Recherche s'organise en effet autour d'une seule (mais fondamentale) hypothèse de travail: c'est dans et par Ia prosodie que pour Vessentiel le langage contribue activement à Ia construction du lien social. La formulation de cette hypothèse resulte des travaux que nous avons menés dans le champ de FAnthropologie des rites, étudiés dans une perspective sémiologique (au sens large), visant à mieux saisir dans quelle mesure et selon quelles modalités, dans et par le rite, Vordre du signe est signe de 1'ordreK Le rite constitue un système complexe de comrpunication symbolique qui contribue en effet activement à definir sur le plan sémantique et à structurer sur le plan dramaturgique les situations d'interaction sociale.

Petites villes européenes au bas Moyen Âge: perspectives de recherche

Fundação para a Ciência e Tecnologia,

Modern optimization in earthwork construction

Earthworks tasks are often regarded in transportation projects as some of the most demanding processes. In fact, sequential tasks such as excavation, transportation, spreading and compaction are strongly based on heavy mechanical equipment and repetitive processes, thus becoming as economically demanding as they are time-consuming. Moreover, actual construction requirements originate higher demands for productivity and safety in earthwork constructions. Given the percentual weight of costs and duration of earthworks in infrastructure construction, the optimal usage of every resource in these tasks is paramount. Considering the characteristics of an earthwork construction, it can be looked at as a production line based on resources (mechanical equipment) and dependency relations between sequential tasks, hence being susceptible to optimization. Up to the present, the steady development of Information Technology areas, such as databases, artificial intelligence and operations research, has resulted in the emergence of several technologies with potential application bearing that purpose in mind. Among these, modern optimization methods (also known as metaheuristics), such as evolutionary computation, have the potential to find high quality optimal solutions with a reasonable use of computational resources. In this context, this work describes an optimization algorithm for earthworks equipment allocation based on a modern optimization approach, which takes advantage of the concept that an earthwork construction can be regarded as a production line.

Le Q-sort, un outil pour la recherche en soins le cas des représentations chez les infirmiers en psychiatrie de l'âge avancé [Q-sort, a useful research method in care in cases of psychiatric nursing of the aged]

Q-sort is a research method which allows defining profiles of attitudes toward a set of statements, ordered in relation to each other. Pertaining to the Q Methodology, the qualitative analysis of the Q-sorts is based on quantitative techniques. This method is of particular interest for research in health professions, a field in which attitudes of patients and professionals are very important. The method is presented in this article, along with an example of application in nursing in old age psychiatry.