« Resolution Search » et problèmes d’optimisation discrète

Thèse réalisée en cotutelle avec l'Université d'Avignon.

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

Modes de conceptualisation métaphoriques et théorie de l’évolution : analyse textuelle et traduction

Éminent naturaliste du XIXe siècle, Charles Darwin publie en 1859 ce qui s'avérera être l’un des textes fondateurs des sciences de la vie : On the origin of species by means of natural selection, or the preservation of favoured races in the struggle for life (ou OS). Ce volumineux ouvrage pose les assises conceptuelles de la théorie darwinienne de l'évolution. Cette dernière suscite encore de nos jours la controverse : certains la nient (créationnisme, dessein intelligent, etc.) alors que d'autres la poussent à l'extrême (eugénisme, darwinisme social, etc.). Vu la grande portée de l'OS, le problème de sa traduction en français se présente de lui-même. Ce champ d'étude reste pourtant largement inexploré. Nous avons donc choisi, dans le présent travail, d’étudier les traductions françaises de l’OS. Notre étude s’inscrivant dans un axe de recherche qui s’intéresse aux modes de conceptualisation métaphorique en usage dans les domaines biomédicaux, ainsi qu’aux problèmes de traduction qu’ils soulèvent, nous avons choisi de nous concentrer plus particulièrement sur les modes de conceptualisation métaphorique présents dans le texte de l'OS, et sur la manière dont ils ont été traduits en français. Pour mener à bien ce projet, nous avons élaboré une méthodologie à partir de celle déjà utilisée avec succès dans des études antérieures menées au sein du même axe de recherche que le nôtre. En plus de l’annotation et l’interrogation informatisée de notre corpus, cette méthodologie consiste en la mise en relation, au plan informatique, de plusieurs traductions d’un même texte. De par sa complexité technique, son élaboration constitue l’un des objectifs majeurs de notre étude. Les résultats obtenus nous ont permis de confirmer deux de nos trois hypothèses : 1) la totalité des modes de conceptualisation identifiés dans notre corpus anglais se retrouvent également dans chacune des traductions, et 2) aucun mode de conceptualisation métaphorique ne peut être dégagé des traductions françaises qui n’est pas déjà présent dans l’original anglais. En plus de nous permettre de comparer chaque traduction à l’original anglais, ces résultats nous ont également permis de comparer entre elles les différentes traductions françaises de l’OS. Ce mémoire de maîtrise comporte six chapitres, qui correspondent tour à tour à : notre cadre théorique, l'état de la question, nos hypothèses et nos objectifs, notre méthodologie, nos résultats et la discussion de ces résultats.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.

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.

Logements insalubres en contexte pluriethnique : étude de cas et pistes d'intervention pour le quartier Norgate dans l'arrondissement Saint-Laurent à Montréal

Ce mémoire explore le rôle du logement dans l'expérience migratoire des nouveaux et nouvelles arrivantes à Montréal et l'impact de celui-ci sur les premières années d'installation, en fonction des caractéristiques socioculturelles des individus. Pour ce faire, une étude collaborative a été menée sur le cas spécifique du quartier de Norgate, situé en plein cœur de l'arrondissement Saint-Laurent. Norgate est un quartier où se produit un renouvellement constant de locataires d'origine immigrante en provenance des quatre coins du monde, et où subsistent d'importants problèmes de pauvreté. En se penchant sur ce milieu de vie et sur les conditions d'habitat de ses résident-e-s, nous avons constaté à quel point un nombre important de locataires vivaient dans des logements en mauvais état, et parfois même dans de graves conditions d'insalubrité. Nous avons cherché à comprendre comment un tel espace urbain pouvait en venir à être aussi dégradé et quels étaient les rôles et responsabilités des différents paliers étatiques face à une telle situation. À travers ce processus, nous avons exploré l'ensemble des possibilités d'action proposées par les différents acteurs (institutionnels, communautaires, résidentiels) ayant un potentiel pouvoir d'agir dans le quartier. Ce mémoire montre comment la problématique des logements dans l'espace urbain est liée à une multitude de facteurs interreliés et qui s'influencent mutuellement, d'où la nécessité d'une approche systémique dans l'analyse du champ de l'anthropologie urbaine. Il cherche également à montrer en quoi un mouvement urbain efficient nécessite un partenariat rigoureux entre les différents acteurs agissant sur le territoire, dans une logique de compréhension et de respect de la diversité des tactiques.

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.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.

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.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

Negative affect mediates the relationship between the Cortisol Awakening Response and Conduct Problems in boys

Ce mémoire débute avec deux chapitres portant sur les problèmes des conduites et la régulation du stress, notamment sur l’axe hypothalamique-pituitaire-surrénal (HPS). Ensuite, la littérature est résumée et nous voyons que les études qui cherchent à établir un lien entre les problèmes des conduites et l’axe HPS ont trouvé des résultats différents et parfois contradictoires. Le chapitre suivant illustre les problèmes méthodologiques qui pourraient expliquer ces résultats différents. Vient ensuite l’étude présentée dans ce mémoire qui cherche à établir un lien entre la réponse cortisolaire à l’éveil (RCE), considérée comme un bon indice du fonctionnent de l’axe HPS, et les problèmes de conduites chez l’enfant. De plus, les émotions négatives ont été associées avec les problèmes des conduites ainsi qu’aux dysfonctions de l’axe HPS, notamment le RCE. L’étude présentée dans ce mémoire cherche aussi à établir si les émotions négatives pourrait être une variable médiatrice dans la relation potentielle entre la RCE et les problèmes des conduites. L’étude révèle que pour les garçons mais pas pour les filles, une RCE réduite est associée avec les émotions négatives, ce qui est successivement associé avec les problèmes des conduites. Le dernier chapitre du mémoire examine les implications théoriques de cette médiatisation et propose également des pistes psychobiologiques pour expliquer les différences sexuelles observées.

Planification et dimensionnement des réseaux optiques de longues distances

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau.

Le développement économique régional, la politique et les disparités régionales des grands territoires : le cas du Canada et de la Chine

Résumé Depuis le début des années 1990, la recherche sur le développement régional a pris une importance considérable dans les disciplines de l’économie et de la géographie dans la plupart des pays. De nombreuses études ont été consacrées à ce sujet et l’on constate une approche analytique de plus en plus sophistiquée. Que les économies pauvres ont tendance à converger vers les pays riches, ou bien à diverger au fil du temps est une question qui a attiré l'attention des décideurs et des universitaires depuis quelques décennies. Convergence ou de divergence économique est un sujet d'intérêt et de débat, non seulement pour valider ou non les deux modèles principaux de croissance qui sont considérés comme concurrent (l’approche néo-classique et celle des approches de croissance endogène), mais aussi pour ses implications pour les publiques politiques. En se basant sur une analyse des politiques de développement régional et des analyses statistiques de la convergence et des disparités régionales, les objectifs de cette thèse sont de tenter de fournir une explication des différents processus et des modèles de développement économique régional poursuivis dans le cas de territoires immenses en utilisant le Canada et la Chine comme études de cas, d'entreprendre une analyse des différents facteurs et des forces motrices qui sous-tendent le développement régional dans ces deux pays, et d'explorer à la fois les réussites et les échecs apparents dans les politiques de développement régional en comparant et contrastant les expériences de développement régional et les modèles de ces deux pays. A fin d'atteindre cet objectif, la recherche utilise une approche multi-scalaire et des méthodes de mesure multidimensionnelle dans le cadre des analyses sur les disparités « régionales » entre les macro régions (sous-ensembles de provinces) des deux pays, des provinces et des régions urbaines sélectionnées, dans le but ultime d’identifier des problèmes existants en termes de développement régional et de pouvoir proposer des solutions. Les étapes principales de la recherche sont : 1. La cueillette des données statistiques pour le Canada et la Chine (incluant les provinces de Québec et de Xinjiang) pour une gamme d’indicateurs (voir ci-dessous). 2. D’entreprendre une analyse de chaque dimension dans les deux juridictions: Population (p.ex. composition, structure, changement); Ressources (p. ex. utilisation, exploitation de l’énergie); Environnement (p.ex. la pollution); et le Développement socioéconomique (p.ex. le développement et la transformation des secteurs clé, et les modèles de développement rural et urbain), et les disparités changeantes par rapport à ces dimensions. 3. La définition d’une typologie de différents types de région en fonction de leurs trajectoires de développement, ce qui servira pour critiquer l’hypothèse centre-périphérie. 4. Le choix d’une région métropolitaine dans chaque juridiction (province). 5. D’entreprendre une analyse temporelle des événements clé (politiques, investissements) dans chaque région et les facteurs impliqués dans chaque événement, en utilisant l’information documentaire générale et des agences institutionnelles impliqués actuellement et dans un passée récent. Cette étude a tenté d'expliquer les schémas et les processus des deux économies, ainsi que la présentation d'études de cas qui illustrent et examinent les différences dans les deux économies à partir de l’échelle nationale jusqu’au niveau régional et provincial et aussi pour certaines zones urbaines. Cette étude a essayé de répondre aux questions de recherche comme: Est-il vrai que les pays avec des plus grandes territoires sont associés avec des plus grandes disparités interrégionales? Quel est le résultat des comparaisons entre pays développés et pays en développement? Quels sont les facteurs les plus importants dans le développement économique de vastes territoires dans les pays développés et pays en développement? Quel est le mécanisme de convergence et de divergence dans les pays développés et, respectivement, les pays en développement? Dans l'introduction à la thèse, le cadre général de l'étude est présenté, suivie dans le chapitre 1 d'une discussion sur les théories et les concepts utilisés dans la littérature théorique principale qui est pertinent à l'étude. Le chapitre 2 décrit la méthodologie de recherche. Le chapitre 3 présente une vue d'ensemble des politiques de développement économique régional et les programmes du Canada et de la Chine dans des périodes différentes à différentes échelles. Au chapitre 4, la convergence des deux pays à l'échelle nationale et la convergence provinciale pour chaque pays sont examinés en utilisant différentes méthodes de mesure telles que les méthodes traditionnelles, la convergence bêta et la convergence sigma. Dans le chapitre le plus complexe, le chapitre 5, les analyses comparatives sont présentées à l'aide de données statistiques, à partir des analyses des cas régionaux et provinciaux retenus des deux pays. Au chapitre 6, ces dispositions sont complétées par une analyse des régions urbaines choisies, qui permet également des aperçus sur les régions les plus périphériques. Dans la recherche proposée pour cette thèse, la politique, la population, le revenu, l'emploi, la composition industrielle, l'investissement, le commerce et le facteur de la migration sont également pris en compte comme facteurs importants de l'analyse régionale compte tenu de la superficie du territoire des deux pays et les différences de population entre eux. Cette thèse a évalué dans quelle mesure les politiques gouvernementales ont réussi à induire la convergence régionale ou ont encore ont creusé davantage les disparités régionales, ce qui implique nécessairement une évaluation de la durabilité des patrons et des programmes de développement régional. Cette étude a également mis l'accent sur les disparités régionales et la politique de développement régional, les comparaisons entre pays, pour mesurer la convergence entre les pays et entre les régions, y compris l'analyse spatiale, d'identifier les facteurs les plus actifs tels que la population, les ressources, la politique, l'urbanisation, les migrations, l'ouverture économique et leurs différents rôles dans le développement économique de ces grands territoires (au Canada et Chine). Les résultats empiriques et les processus de convergence et de divergence offrent un cadre intéressant pour l'examen de la trajectoire de développement régionales et les disparités régionales dans les deux économies. L'approche adoptée a révélé les différentes mosaïques complexes du développement régional dans les deux pays. Les résultats de cette étude ont démontré que la disparité en termes de revenu régional est une réalité dans chaque zone géographique, et que les causes sont nombreuses et complexes. Les deux économies ont certains parallèles dans la mise en œuvre des politiques de développement économique régional, mais il existe des différences importantes aussi et elles se sont développées à différentes vitesses. Les deux économies se sont développées depuis la Seconde Guerre mondiale, mais la Chine a connu une croissance rapide que le Canada comme témoignent de nombreux indicateurs depuis 1980. Cependant, la Chine est maintenant confrontée à un certain nombre de problèmes économiques et sociaux, y compris les disparités régionales marquées, un fossé toujours croissant entre les revenus ruraux et urbains, une population vieillissante, le chômage, la pauvreté et la dégradation rapide de l'environnement avec toujours plus de demandes en énergie. Le développement économique régional en Chine est plus déséquilibré. Le Canada accuse un degré de disparités régionales et provinciales moins important que la Chine. Dans les cas provinciaux, il existe d'importantes différences et de disparités dans la structure économique et spatiale du Québec et du Xinjiang. Les disparités infra provinciales sont plus grandes que celles à l’échelle des provinces et des grandes régions (des sous-ensembles de provinces). Les mécanismes de convergence et de divergence dans les deux pays sont différents. Les résultats empiriques et les processus de convergence et de divergence offrent un cadre intéressant pour l'examen de la trajectoire de développement régionale et les disparités régionales dans les deux économies. Cette étude démontre également que l'urbanisation (les métropoles et les villes) s’avère être le facteur le plus actif et contribue à l'économie régionale dans ces grands territoires. L'ouverture a joué un rôle important dans les économies des deux pays. La migration est un facteur majeur dans la stimulation de l'économie des deux pays mais de façons différentes. Les résultats empiriques démontrent que les disparités régionales ne peuvent pas être évitées et elles existent presque partout. Il n'y a pas une formule universelle et de politiques spécifiques sont de mise pour chaque région. Mais il semble possible pour les décideurs politiques nationaux et régionaux d’essayer de maintenir l'écart à une échelle raisonnable pour éviter l'instabilité sociale.