Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

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.

Réduction des artéfacts de tuteur coronarien au moyen d’un algorithme de reconstruction avec renforcement des bords : étude prospective transversale en tomodensitométrie 256 coupes

Les artéfacts métalliques entraînent un épaississement artéfactuel de la paroi des tuteurs en tomodensitométrie (TDM) avec réduction apparente de leur lumière. Cette étude transversale prospective, devis mesures répétées et observateurs avec méthode en aveugle, chez 24 patients consécutifs/71 tuteurs coronariens a pour objectif de comparer l’épaisseur de paroi des tuteurs en TDM après reconstruction par un algorithme avec renforcement des bords et un algorithme standard. Une angiographie coronarienne par TDM 256 coupes a été réalisée, avec reconstruction par algorithmes avec renforcement des bords et standard. L’épaisseur de paroi des tuteurs était mesurée par méthodes orthogonale (diamètres) et circonférentielle (circonférences). La qualité d’image des tuteurs était évaluée par échelle ordinale, et les données analysées par modèles linéaire mixte et régression logistique des cotes proportionnelles. L’épaisseur de paroi des tuteurs était inférieure avec l’algorithme avec renforcement des bords comparé à l’algorithme standard, avec les méthodes orthogonale (0,97±0,02 vs 1,09±0,03 mm, respectivement; p<0,001) et circonférentielle (1,13±0,02 vs 1,21±0,02 mm, respectivement; p<0,001). Le premier causait moins de surestimation par rapport à l’épaisseur nominale comparé au second, avec méthodes orthogonale (0,89±0,19 vs 1,00±0,26 mm, respectivement; p<0,001) et circonférentielle (1,06±0,26 vs 1,13±0,31 mm, respectivement; p=0,005) et diminuait de 6 % la surestimation. Les scores de qualité étaient meilleurs avec l’algorithme avec renforcement des bords (OR 3,71; IC 95% 2,33–5,92; p<0,001). En conclusion, la reconstruction des images avec l’algorithme avec renforcement des bords génère des parois de tuteurs plus minces, moins de surestimation, et de meilleurs scores de qualité d’image que l’algorithme standard.

GLS Detrending, Efficient Unit Root Tests and Structural Change

We extend the class of M-tests for a unit root analyzed by Perron and Ng (1996) and Ng and Perron (1997) to the case where a change in the trend function is allowed to occur at an unknown time. These tests M(GLS) adopt the GLS detrending approach of Dufour and King (1991) and Elliott, Rothenberg and Stock (1996) (ERS). Following Perron (1989), we consider two models : one allowing for a change in slope and the other for both a change in intercept and slope. We derive the asymptotic distribution of the tests as well as that of the feasible point optimal tests PT(GLS) suggested by ERS. The asymptotic critical values of the tests are tabulated. Also, we compute the non-centrality parameter used for the local GLS detrending that permits the tests to have 50% asymptotic power at that value. We show that the M(GLS) and PT(GLS) tests have an asymptotic power function close to the power envelope. An extensive simulation study analyzes the size and power in finite samples under various methods to select the truncation lag for the autoregressive spectral density estimator. An empirical application is also provided.

Simulation-Based Finite-and Large-sample Inference Methods in Multivariate Regressions and Seemingly Unrelated Regressions

In the context of multivariate regression (MLR) and seemingly unrelated regressions (SURE) models, it is well known that commonly employed asymptotic test criteria are seriously biased towards overrejection. in this paper, we propose finite-and large-sample likelihood-based test procedures for possibly non-linear hypotheses on the coefficients of MLR and SURE systems.

The FCLT with Dependent Errors: an Helicopter Tour of the Quality of the Approximation

This note investigates the adequacy of the finite-sample approximation provided by the Functional Central Limit Theorem (FCLT) when the errors are allowed to be dependent. We compare the distribution of the scaled partial sums of some data with the distribution of the Wiener process to which it converges. Our setup is purposely very simple in that it considers data generated from an ARMA(1,1) process. Yet, this is sufficient to bring out interesting conclusions about the particular elements which cause the approximations to be inadequate in even quite large sample sizes.

Méthodes d’inférence exactes pour un modèle de régression avec erreurs AR(2) gaussiennes

Ce texte propose des méthodes d’inférence exactes (tests et régions de confiance) sur des modèles de régression linéaires avec erreurs autocorrélées suivant un processus autorégressif d’ordre deux [AR(2)], qui peut être non stationnaire. L’approche proposée est une généralisation de celle décrite dans Dufour (1990) pour un modèle de régression avec erreurs AR(1) et comporte trois étapes. Premièrement, on construit une région de confiance exacte pour le vecteur des coefficients du processus autorégressif (φ). Cette région est obtenue par inversion de tests d’indépendance des erreurs sur une forme transformée du modèle contre des alternatives de dépendance aux délais un et deux. Deuxièmement, en exploitant la dualité entre tests et régions de confiance (inversion de tests), on détermine une région de confiance conjointe pour le vecteur φ et un vecteur d’intérêt M de combinaisons linéaires des coefficients de régression du modèle. Troisièmement, par une méthode de projection, on obtient des intervalles de confiance «marginaux» ainsi que des tests à bornes exacts pour les composantes de M. Ces méthodes sont appliquées à des modèles du stock de monnaie (M2) et du niveau des prix (indice implicite du PNB) américains

Tests multiples simulés et tests de normalité basés sur plusieurs moments dans les modèles de régression

Cet article illustre l’applicabilité des méthodes de rééchantillonnage dans le cadre des tests multiples (simultanés), pour divers problèmes économétriques. Les hypothèses simultanées sont une conséquence habituelle de la théorie économique, de sorte que le contrôle de la probabilité de rejet de combinaisons de tests est un problème que l’on rencontre fréquemment dans divers contextes économétriques et statistiques. À ce sujet, on sait que le fait d’ignorer le caractère conjoint des hypothèses multiples peut faire en sorte que le niveau de la procédure globale dépasse considérablement le niveau désiré. Alors que la plupart des méthodes d’inférence multiple sont conservatrices en présence de statistiques non-indépendantes, les tests que nous proposons visent à contrôler exactement le niveau de signification. Pour ce faire, nous considérons des critères de test combinés proposés initialement pour des statistiques indépendantes. En appliquant la méthode des tests de Monte Carlo, nous montrons comment ces méthodes de combinaison de tests peuvent s’appliquer à de tels cas, sans recours à des approximations asymptotiques. Après avoir passé en revue les résultats antérieurs sur ce sujet, nous montrons comment une telle méthodologie peut être utilisée pour construire des tests de normalité basés sur plusieurs moments pour les erreurs de modèles de régression linéaires. Pour ce problème, nous proposons une généralisation valide à distance finie du test asymptotique proposé par Kiefer et Salmon (1983) ainsi que des tests combinés suivant les méthodes de Tippett et de Pearson-Fisher. Nous observons empiriquement que les procédures de test corrigées par la méthode des tests de Monte Carlo ne souffrent pas du problème de biais (ou sous-rejet) souvent rapporté dans cette littérature – notamment contre les lois platikurtiques – et permettent des gains sensibles de puissance par rapport aux méthodes combinées usuelles.

Estimation des modèles à seuil STAR et SETAR par deux méthodes d'estimation indirecte.

Rapport de recherche

La discrimination sur le marché du travail italien. Une comparaison des différentes méthodes d'estimation.

Rapport de recherche

Développement et validation de méthodes visant une utilisation optimale d'antennes réceptrices en imagerie par résonance magnétique

Différentes méthodes ayant pour objectif une utilisation optimale d'antennes radio-fréquences spécialisées en imagerie par résonance magnétique sont développées et validées. Dans un premier temps, il est démontré qu'une méthode alternative de combinaison des signaux provenant des différents canaux de réception d'un réseau d'antennes mène à une réduction significative du biais causé par la présence de bruit dans des images de diffusion, en comparaison avec la méthode de la somme-des-carrés généralement utilisée. Cette réduction du biais engendré par le bruit permet une amélioration de l'exactitude de l'estimation de différents paramètres de diffusion et de diffusion tensorielle. De plus, il est démontré que cette méthode peut être utilisée conjointement avec une acquisition régulière sans accélération, mais également en présence d'imagerie parallèle. Dans une seconde perspective, les bénéfices engendrés par l'utilisation d'une antenne d'imagerie intravasculaire sont étudiés. Suite à une étude sur fantôme, il est démontré que l'imagerie par résonance magnétique intravasculaire offre le potentiel d'améliorer significativement l'exactitude géométrique lors de mesures morphologiques vasculaires, en comparaison avec les résultats obtenus avec des antennes de surface classiques. Il est illustré qu'une exactitude géométrique comparable à celle obtenue grâce à une sonde ultrasonique intravasculaire peut être atteinte. De plus, plusieurs protocoles basés sur une acquisition de type balanced steady-state free-precession sont comparés dans le but de mettre en évidence différentes relations entre les paramètres utilisés et l'exactitude géométrique obtenue. En particulier, des dépendances entre la taille du vaisseau, le rapport signal-sur-bruit à la paroi vasculaire, la résolution spatiale et l'exactitude géométrique atteinte sont mises en évidence. Dans une même optique, il est illustré que l'utilisation d'une antenne intravasculaire permet une amélioration notable de la visualisation de la lumière d'une endoprothèse vasculaire. Lorsque utilisée conjointement avec une séquence de type balanced steady-state free-precession utilisant un angle de basculement spécialement sélectionné, l'imagerie par résonance magnétique intravasculaire permet d'éliminer complètement les limitations normalement engendrées par l'effet de blindage radio-fréquence de l'endoprothèse.

Développement de méthodes d’analyse directe de polluants organiques volatils à l’état de traces dans l’air et les biogaz

Il est reconnu que le benzène, le toluène, l’éthylbenzène et les isomères du xylène, composés organiques volatils (COVs) communément désignés BTEX, produisent des effets nocifs sur la santé humaine et sur les végétaux dépendamment de la durée et des niveaux d’exposition. Le benzène en particulier est classé cancérogène et une exposition à des concentrations supérieures à 64 g/m3 de benzène peut être fatale en 5–10 minutes. Par conséquent, la mesure en temps réel des BTEX dans l’air ambiant est essentielle pour détecter rapidement un danger associé à leur émission dans l’air et pour estimer les risques potentiels pour les êtres vivants et pour l’environnement. Dans cette thèse, une méthode d’analyse en temps réel des BTEX dans l’air ambiant a été développée et validée. La méthode est basée sur la technique d’échantillonnage direct de l’air couplée avec la spectrométrie de masse en tandem utilisant une source d’ionisation chimique à pression atmosphérique (APCI-MS/MS directe). La validation analytique a démontré la sensibilité (limite de détection LDM 1–2 μg/m3), la précision (coefficient de variation CV < 10%), l’exactitude (exactitude > 95%) et la sélectivité de la méthode. Des échantillons d’air ambiant provenant d’un site d’enfouissement de déchets industriels et de divers garages d’entretien automobile ont été analysés par la méthode développée. La comparaison des résultats avec ceux obtenus par la technique de chromatographie gazeuse on-line couplée avec un détecteur à ionisation de flamme (GC-FID) a donné des résultats similaires. La capacité de la méthode pour l’évaluation rapide des risques potentiels associés à une exposition aux BTEX a été prouvée à travers une étude de terrain avec analyse de risque pour la santé des travailleurs dans trois garages d’entretien automobile et par des expériences sous atmosphères simulées. Les concentrations mesurées dans l’air ambiant des garages étaient de 8,9–25 µg/m3 pour le benzène, 119–1156 µg/m3 pour le toluène, 9–70 µg/m3 pour l’éthylbenzène et 45–347 µg/m3 pour les xylènes. Une dose quotidienne environnementale totale entre 1,46 10-3 et 2,52 10-3 mg/kg/jour a été déterminée pour le benzène. Le risque de cancer lié à l’exposition environnementale totale au benzène estimé pour les travailleurs étudiés se situait entre 1,1 10-5 et 1,8 10-5. Une nouvelle méthode APCI-MS/MS a été également développée et validée pour l’analyse directe de l’octaméthylcyclotétrasiloxane (D4) et le décaméthylcyclopentasiloxane (D5) dans l’air et les biogaz. Le D4 et le D5 sont des siloxanes cycliques volatils largement utilisés comme solvants dans les processus industriels et les produits de consommation à la place des COVs précurseurs d’ozone troposphérique tels que les BTEX. Leur présence ubiquitaire dans les échantillons d’air ambiant, due à l’utilisation massive, suscite un besoin d’études de toxicité. De telles études requièrent des analyses qualitatives et quantitatives de traces de ces composés. Par ailleurs, la présence de traces de ces substances dans un biogaz entrave son utilisation comme source d’énergie renouvelable en causant des dommages coûteux à l’équipement. L’analyse des siloxanes dans un biogaz s’avère donc essentielle pour déterminer si le biogaz nécessite une purification avant son utilisation pour la production d’énergie. La méthode développée dans cette étude possède une bonne sensibilité (LDM 4–6 μg/m3), une bonne précision (CV < 10%), une bonne exactitude (> 93%) et une grande sélectivité. Il a été également démontré qu’en utilisant cette méthode avec l’hexaméthyl-d18-disiloxane comme étalon interne, la détection et la quantification du D4 et du D5 dans des échantillons réels de biogaz peuvent être accomplies avec une meilleure sensibilité (LDM ~ 2 μg/m3), une grande précision (CV < 5%) et une grande exactitude (> 97%). Une variété d’échantillons de biogaz prélevés au site d’enfouissement sanitaire du Complexe Environnemental de Saint-Michel à Montréal a été analysée avec succès par cette nouvelle méthode. Les concentrations mesurées étaient de 131–1275 µg/m3 pour le D4 et 250–6226 µg/m3 pour le D5. Ces résultats représentent les premières données rapportées dans la littérature sur la concentration des siloxanes D4 et D5 dans les biogaz d’enfouissement en fonction de l’âge des déchets.