Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.

Relative Uncertainty and Additively Representable Set Rankings

This paper proposes a definition of relative uncertainty aversion for decision models under complete uncertainty. It is shown that, for a large class of decision rules characterized by a set of plausible axioms, the new criterion yields a complete ranking of those rules with respect to the relative degree of uncertainty aversion they represent. In addition, we address a combinatorial question that arises in this context, and we examine conditions for the additive representability of our rules.

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

Changes in cortical and sub-cortical patterns of activity associated with aging during the performance of a lexical set-shifting task

Bien que le passage du temps altère le cerveau, la cognition ne suit pas nécessairement le même destin. En effet, il existe des mécanismes compensatoires qui permettent de préserver la cognition (réserve cognitive) malgré le vieillissement. Les personnes âgées peuvent utiliser de nouveaux circuits neuronaux (compensation neuronale) ou des circuits existants moins susceptibles aux effets du vieillissement (réserve neuronale) pour maintenir un haut niveau de performance cognitive. Toutefois, la façon dont ces mécanismes affectent l’activité corticale et striatale lors de tâches impliquant des changements de règles (set-shifting) et durant le traitement sémantique et phonologique n’a pas été extensivement explorée. Le but de cette thèse est d’explorer comment le vieillissement affecte les patrons d’activité cérébrale dans les processus exécutifs d’une part et dans l’utilisation de règles lexicales d’autre part. Pour cela nous avons utilisé l’imagerie par résonance magnétique fonctionnelle (IRMf) lors de la performance d’une tâche lexicale analogue à celle du Wisconsin. Cette tâche a été fortement liée à de l’activité fronto-stritale lors des changements de règles, ainsi qu’à la mobilisation de régions associées au traitement sémantique et phonologique lors de décisions sémantiques et phonologiques, respectivement. Par conséquent, nous avons comparé l’activité cérébrale de jeunes individus (18 à 35 ans) à celle d’individus âgés (55 à 75 ans) lors de l’exécution de cette tâche. Les deux groupes ont montré l’implication de boucles fronto-striatales associées à la planification et à l’exécution de changements de règle. Toutefois, alors que les jeunes semblaient activer une « boucle cognitive » (cortex préfrontal ventrolatéral, noyau caudé et thalamus) lorsqu’ils se voyaient indiquer qu’un changement de règle était requis, et une « boucle motrice » (cortex postérieur préfrontal et putamen) lorsqu’ils devaient effectuer le changement, les participants âgés montraient une activation des deux boucles lors de l’exécution des changements de règle seulement. Les jeunes adultes tendaient à présenter une augmentation de l’activité du cortex préfrontal ventrolatéral, du gyrus fusiforme, du lobe ventral temporale et du noyau caudé lors des décisions sémantiques, ainsi que de l’activité au niveau de l’aire de Broca postérieur, de la junction temporopariétale et du cortex moteur lors de décisions phonologiques. Les participants âgés ont montré de l’activité au niveau du cortex préfrontal latéral et moteur durant les deux types de décisions lexicales. De plus, lorsque les décisions sémantiques et phonologiques ont été comparées entre elles, les jeunes ont montré des différences significatives au niveau de plusieurs régions cérébrales, mais pas les âgés. En conclusion, notre première étude a montré, lors du set-shifting, un délai de l’activité cérébrale chez les personnes âgées. Cela nous a permis de conceptualiser l’Hypothèse Temporelle de Compensation (troisième manuscrit) qui consiste en l’existence d’un mécanisme compensatoire caractérisé par un délai d’activité cérébrale lié au vieillissement permettant de préserver la cognition au détriment de la vitesse d’exécution. En ce qui concerne les processus langagiers (deuxième étude), les circuits sémantiques et phonologiques semblent se fusionner dans un seul circuit chez les individus âgés, cela représente vraisemblablement des mécanismes de réserve et de compensation neuronales qui permettent de préserver les habilités langagières.

Wittgenstein And Labyrinth Of ‘Actual Infinity’: The Critique Of Transfinite Set Theory

In order to explain Wittgenstein’s account of the reality of completed infinity in mathematics, a brief overview of Cantor’s initial injection of the idea into set- theory, its trajectory (including the Diagonal Argument, the Continuum Hypothesis and Cantor’s Theorem) and the philosophic implications he attributed to it will be presented. Subsequently, we will first expound Wittgenstein’s grammatical critique of the use of the term ‘infinity’ in common parlance and its conversion into a notion of an actually existing (completed) infinite ‘set’. Secondly, we will delve into Wittgenstein’s technical critique of the concept of ‘denumerability’ as it is presented in set theory as well as his philosophic refutation of Cantor’s Diagonal Argument and the implications of such a refutation onto the problems of the Continuum Hypothesis and Cantor’s Theorem. Throughout, the discussion will be placed within the historical and philosophical framework of the Grundlagenkrise der Mathematik and Hilbert’s problems.