Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Apport d’une évaluation biomécanique 3D du genou dans la prise en charge orthopédique de patients ayant une rupture du ligament croisé antérieur

Parmi les blessures sportives reliées au genou, 20 % impliquent le ligament croisé antérieur (LCA). Le LCA étant le principal stabilisateur du genou, une lésion à cette structure engendre une importante instabilité articulaire influençant considérablement la fonction du genou. L’évaluation clinique actuelle des patients ayant une atteinte au LCA présente malheureusement des limitations importantes à la fois dans l’investigation de l’impact de la blessure et dans le processus diagnostic. Une évaluation biomécanique tridimensionnelle (3D) du genou pourrait s’avérer une avenue innovante afin de pallier à ces limitations. L’objectif général de la thèse est de démontrer la valeur ajoutée du domaine biomécanique dans (1) l’investigation de l’impact de la blessure sur la fonction articulaire du genou et dans (2) l’aide au diagnostic. Pour répondre aux objectifs de recherche un groupe de 29 patients ayant une rupture du LCA (ACLD) et un groupe contrôle de 15 participants sains ont pris part à une évaluation biomécanique 3D du genou lors de tâches de marche sur tapis roulant. L’évaluation des patrons biomécaniques 3D du genou a permis de démontrer que les patients ACLD adoptent un mécanisme compensatoire que nous avons intitulé pivot-shift avoidance gait. Cette adaptation biomécanique a pour objectif d’éviter de positionner le genou dans une condition susceptible de provoquer une instabilité antérolatérale du genou lors de la marche. Par la suite, une méthode de classification a été développée afin d’associer de manière automatique et objective des patrons biomécaniques 3D du genou soit au groupe ACLD ou au groupe contrôle. Pour cela, des paramètres ont été extraits des patrons biomécaniques en utilisant une décomposition en ondelettes et ont ensuite été classifiés par la méthode du plus proche voisin. Notre méthode de classification a obtenu un excellent niveau précision, de sensibilité et de spécificité atteignant respectivement 88%, 90% et 87%. Cette méthode a donc le potentiel de servir d’outil d’aide à la décision clinique. La présente thèse a démontré l’apport considérable d’une évaluation biomécanique 3D du genou dans la prise en charge orthopédique de patients présentant une rupture du LCA; plus spécifiquement dans l’investigation de l’impact de la blessure et dans l’aide au diagnostic.

L’évolution de la qualité d’emploi des immigrants du Canada par rapport aux natifs : une comparaison interprovinciale

Il est bien connu que les immigrants rencontrent plusieurs difficultés d’intégration dans le marché du travail canadien. Notamment, ils gagnent des salaires inférieurs aux natifs et ils sont plus susceptibles que ces derniers d’occuper des emplois précaires ou pour lesquels ils sont surqualifiés. Dans cette recherche, nous avons traité de ces trois problèmes sous l’angle de la qualité d’emploi. À partir des données des recensements de la population de 1991 à 2006, nous avons comparé l’évolution de la qualité d’emploi des immigrants et des natifs au Canada, mais aussi au Québec, en Ontario et en Colombie-Britannique. Ces comparaisons ont mis en évidence la hausse du retard de qualité d’emploi des immigrants par rapport aux natifs dans tous les lieux analysés, mais plus particulièrement au Québec. Le désavantage des immigrants persiste même lorsqu’on tient compte du capital humain, des caractéristiques démographiques et du taux de chômage à l’entrée dans le marché du travail. La scolarité, l’expérience professionnelle globale et les connaissances linguistiques améliorent la qualité d’emploi des immigrants et des natifs. Toutefois, lorsqu’on fait la distinction entre l’expérience de travail canadienne et l’expérience de travail étrangère, on s’aperçoit que ce dernier type d’expérience réduit la qualité d’emploi des immigrants. Dans ces circonstances, nous trouvons incohérent que le Canada et le Québec continuent à insister sur ce critère dans leur grille de sélection des travailleurs qualifiés. Pour valoriser les candidats les plus jeunes ayant peu d’expérience de travail dans leur pays d’origine, nous suggérons d’accroître l’importance accordée à l’âge dans ces grilles au détriment de l’expérience. Les jeunes, les étudiants étrangers et les travailleurs temporaires qui possèdent déjà une expérience de travail au Canada nous apparaissent comme des candidats à l’immigration par excellence. Par contre, les résultats obtenus à l’aide de la méthode de décomposition de Blinder-Oaxaca ont montré que l’écart de qualité d’emploi entre les immigrants et les natifs découle d’un traitement défavorable envers les immigrants dans le marché du travail. Cela signifie que les immigrants sont pénalisés au chapitre de la qualité d’emploi à la base, et ce, peu importe leurs caractéristiques. Dans ce contexte, la portée de tout ajustement aux grilles de sélection risque d’être limitée. Nous proposons donc d’agir également en aval du problème à l’aide des politiques d’aide à l’intégration des immigrants. Pour ce faire, une meilleure concertation entre les acteurs du marché du travail est nécessaire. Les ordres professionnels, le gouvernement, les employeurs et les immigrants eux-mêmes doivent s’engager afin d’établir des parcours accélérés pour la reconnaissance des compétences des nouveaux arrivants. Nos résultats indiquent aussi que le traitement défavorable à l’égard des immigrants dans le marché du travail est plus prononcé au Québec qu’en Ontario et en Colombie-Britannique. Il se peut que la société québécoise soit plus réfractaire à l’immigration vu son caractère francophone et minoritaire dans le reste de l’Amérique du Nord. Pourtant, le désir de protéger la langue française motive le Québec à s’impliquer activement en matière d’immigration depuis longtemps et la grille de sélection québécoise insiste déjà sur ce critère. D’ailleurs, près des deux tiers des nouveaux arrivants au Québec connaissent le français en 2011.

Analyse de maillages surfaciques par construction et comparaison de modèles moyens et par décomposition par graphes s’appuyant sur les courbures discrètes : application à l’étude de la cornée humaine

Réalisé en cotutelle avec Aix Marseille Université.

Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

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.