Choix d'un associateur 2-D pour le balayage multiple et optimisation de l'estimation des pistes

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Anisotropy of spin relaxation of water protons in cartilage and tendon

Transverse spin relaxation rates of water protons in articular cartilage and tendon depend on the orientation of the tissue relative to the applied static magnetic field. This complicates the interpretation of magnetic resonance images of these tissues. At the same time, relaxation data can provide information about their organisation and microstructure. We present a theoretical analysis of the anisotropy of spin relaxation of water protons observed in fully hydrated cartilage. We demonstrate that the anisotropy of transverse relaxation is due almost entirely to intramolecular dipolar coupling modulated by a specific mode of slow molecular motion: the diffusion of water molecules in the hydration shell of a collagen fibre around the fibre, such that the molecular director remains perpendicular to the fibre. The theoretical anisotropy arising from this mechanism follows the “magic-angle” dependence observed in magnetic-resonance measurements of cartilage and tendon and is in good agreement with the available experimental results. We discuss the implications of the theoretical findings for MRI of ordered collagenous tissues.

Investigation of 'off-line‘ relaxation phenomena in oil filled transformers

Power transformers are one of the most important and costly equipment in power generation, transmission and distribution systems. Current average age of transformers in Australia is around 25 years and there is a strong economical tendency to use them up to 50 years or more. As the transformers operate, they get degraded due to different loading and environmental operating stressed conditions. In today‘s competitive energy market with the penetration of distributed energy sources, the transformers are stressed more with minimum required maintenance. The modern asset management program tries to increase the usage life time of power transformers with prognostic techniques using condition indicators. In the case of oil filled transformers, condition monitoring methods based on dissolved gas analysis, polarization studies, partial discharge studies, frequency response analysis studies to check the mechanical integrity, IR heat monitoring and other vibration monitoring techniques are in use. In the current research program, studies have been initiated to identify the degradation of insulating materials by the electrical relaxation technique known as dielectrometry. Aging leads to main degradation products like moisture and other oxidized products due to fluctuating thermal and electrical loading. By applying repetitive low frequency high voltage sine wave perturbations in the range of 100 to 200 V peak across available terminals of power transformer, the conductive and polarization parameters of insulation aging are identified. An in-house novel digital instrument is developed to record the low leakage response of repetitive polarization currents in three terminals configuration. The technique is tested with known three transformers of rating 5 kVA or more. The effects of stressing polarization voltage level, polarizing wave shapes and various terminal configurations provide characteristic aging relaxation information. By using different analyses, sensitive parameters of aging are identified and it is presented in this thesis.

Age-related loss of brain volume and T2 relaxation time in youth with type 1 diabetes

OBJECTIVE: Childhood-onset type 1 diabetes is associated with neurocognitive deficits, but there is limited evidence to date regarding associated neuroanatomical brain changes and their relationship to illness variables such as age at disease onset. This report examines age-related changes in volume and T2 relaxation time (a fundamental parameter of magnetic resonance imaging that reflects tissue health) across the whole brain. RESEARCH DESIGN AND METHODS: Type 1 diabetes, N = 79 (mean age 20.32 ± 4.24 years), and healthy control participants, N = 50 (mean age 20.53 ± 3.60 years). There were no substantial group differences on socioeconomic status, sex ratio, or intelligence quotient. RESULTS: Regression analyses revealed a negative correlation between age and brain changes, with decreasing gray matter volume and T2 relaxation time with age in multiple brain regions in the type 1 diabetes group. In comparison, the age-related decline in the control group was small. Examination of the interaction of group and age confirmed a group difference (type 1 diabetes vs. control) in the relationship between age and brain volume/T2 relaxation time. CONCLUSIONS: We demonstrated an interaction between age and group in predicting brain volumes and T2 relaxation time such that there was a decline in these outcomes in type 1 diabetic participants that was much less evident in control subjects. Findings suggest the neurodevelopmental pathways of youth with type 1 diabetes have diverged from those of their healthy peers by late adolescence and early adulthood but the explanation for this phenomenon remains to be clarified.

133Cs relaxation times in rat tissues

133Cs relaxation-time studies of tissues from rats into which cesium has been incorporated by dietary loading have been carried out in vivo and in vitro. Whereas tissue T1 values are on the order of seconds, T2 values are as low as a few tens of milliseconds, 133Cs tissue relaxation times are analogous to those of 39K in the same tissues, but are more readily measured because of the greater sensitivity of 133Cs compared with 39K, T1 and T2 data of excised tissue at two resonance frequencies (65.60 and 39.37 MHz) and temperatures (302 and 278 K) have been analyzed in terms of a general description of spin- relaxation. The results are consistent with most of the cesium ions being in a free state, undergoing fast exchange with bound ions having long correlation times located in one or more intracellular compartments,

NMR measurement of 39K detectability and relaxation constants in rat tissue

Differences in the NMR detectability of 39K in various excised rat tissues (liver, brain, kidney, muscle, and testes) have been observed. The lowest NMR detectability occurs for liver (61 ± 3% of potassium as measured by flame photometry) and highest for erythrocytes (100 ± 7%). These differences in detectability correlate with differences in the measured 39K NMR relaxation constants in the same tissues. 39K detectabilities were also found to correlate inversely with the mitochondrial content of the tissues. Mitochondria prepared from liver showed greatly reduced 39K NMR detectability when compared with the tissue from which it was derived, 31.6 ± 9% of potassium measured by flame photometry compared to 61 ± 3%. The detectability of potassium in mitochondria was too low to enable the measurement of relaxation constants. This study indicates that differences in tissue structure, particularly mitochondrial content are important in determining 39K detectability and measured relaxation rates.

NMR relaxation behavior and quadrupole coupling constants of 39K and 23Na ions in glycerol. Comparisons with 39K tissue data

The quadrupole coupling constants (qcc) for39K and23Na ions in glycerol have been calculated from linewidths measured as a function of temperature (which in turn results in changes in solution viscosity). The qcc of39K in glycerol is found to be 1.7 MHz, and that of23Na is 1.6 MHz. The relaxation behavior of39K and23Na ions in glycerol shows magnetic field and temperature dependence consistent with the equations for transverse relaxation more commonly used to describe the reorientation of nuclei in a molecular framework with intramolecular field gradients. It is shown, however, that τc is not simply proportional to the ratio of viscosity/temperature (ηT). The 39K qcc in glycerol and the value of 1.3 MHz estimated for this nucleus in aqueous solution are much greater than values of 0.075 to 0.12 MHz calculated from T2 measurements of39K in freshly excised rat tissues. This indicates that, in biological samples, processes such as exchange of potassium between intracellular compartments or diffusion of ions through locally ordered regions play a significant role in determining the effective quadrupole coupling constant and correlation time governing39K relaxation. T1 and T2 measurements of rat muscle at two magnetic fields also indicate that a more complex correlation function may be required to describe the relaxation of39K in tissue. Similar results and conclusions are found for23Na.