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.

Code-Switching Between Cultures And Languages : Creative connectivity

Problème: Ma thèse porte sur l’identité individuelle comme interrogation sur les enjeux personnels et sur ce qui constitue l’identification hybride à l’intérieur des notions concurrentielles en ce qui a trait à l’authenticité. Plus précisément, j’aborde le concept des identifications hybrides en tant que zones intermédiaires pour ce qui est de l’alternance de codes linguistiques et comme négociation des espaces continuels dans leur mouvement entre les cultures et les langues. Une telle négociation engendre des tensions et/ou apporte le lien créatif. Les tensions sont inhérentes à n’importe quelle construction d’identité où les lignes qui définissent des personnes ne sont pas spécifiques à une culture ou à une langue, où des notions de l’identité pure sont contestées et des codes communs de l’appartenance sont compromis. Le lien créatif se produit dans les exemples où l’alternance de code linguistique ou la négociation des espaces produit le mouvement ouvert et fluide entre les codes de concurrence des références et les différences à travers les discriminations raciales, la sexualité, la culture et la langue. Les travaux que j’ai sélectionnés représentent une section transversale de quelques auteurs migrants provenant de la minorité en Amérique du Nord qui alternent les codes linguistiques de cette manière. Les travaux détaillent le temps et l’espace dans leur traitement de l’identité et dans la façon dont ils cernent l’hybridité dans les textes suivants : The Woman Warrior de Maxine Hong Kingston (1975-76), Hunger of Memory de Richard Rodriguez (1982), Comment faire l’amour avec un nègre sans se fatiguer de Dany Laferrière (1985), Borderlands/La Frontera de Gloria Anzalduá (1987), Lost in Translation de Eva Hoffman (1989), Avril ou l’anti-passion de Antonio D’Alfonso (1990) et Chorus of Mushrooms de Hiromi Goto (1994). Enjeux/Questions La notion de l’identification hybride est provocante comme sujet. Elle met en question l’identité pure. C’est un sujet qui a suscité beaucoup de discussions tant en ce qui a trait à la littérature, à la politique, à la société, à la linguistique, aux communications, qu’au sein même des cercles philosophiques. Ce sujet est compliqué parce qu’il secoue la base des espaces fixes et structurés de l’identité dans sa signification culturelle et linguistique. Par exemple, la notion de patrie n’a pas les représentations exclusives du pays d’origine ou du pays d’accueil. De même, les notions de race, d’appartenance ethnique, et d’espaces sexuels sont parfois négativement acceptées si elles proviennent des codes socialement admis et normalisés de l’extérieur. De tels codes de la signification sont souvent définis par l’étiquette d’identification hétérosexuelle et blanche. Dans l’environnement généralisé d’aujourd’hui, plus que jamais, une personne doit négocier qui elle est, au sens de son appartenance à soi, en tant qu’individu et ce, face aux modèles locaux, régionaux, nationaux, voire même globaux de la subjectivité. Nous pouvons interpréter ce mouvement comme une série de couches superposées de la signification. Quand nous rencontrons une personne pour la première fois, nous ne voyons que la couche supérieure. D’ailleurs, son soi intérieur est caché par de nombreuses couches superposées (voir Joseph D. Straubhaar). Toutefois, sous cette couche supérieure, on retrouve beaucoup d’autres couches et tout comme pour un oignon, on doit les enlever une par une pour que l’individualité complète d’une personne soit révélée et comprise. Le noyau d’une personne représente un point de départ crucial pour opposer qui elle était à la façon dont elle se transforme sans cesse. Sa base, ou son noyau, dépend du moment, et comprend, mais ne s’y limite pas, ses origines, son environnement et ses expériences d’enfance, son éducation, sa notion de famille, et ses amitiés. De plus, les notions d’amour-propre et d’amour pour les autres, d’altruisme, sont aussi des points importants. Il y a une relation réciproque entre le soi et l’autre qui établit notre degré d’estime de soi. En raison de la mondialisation, notre façon de comprendre la culture, en fait, comment on consomme et définit la culture, devient rapidement un phénomène de déplacement. À l’intérieur de cette arène de culture généralisée, la façon dont les personnes sont à l’origine chinoises, mexicaines, italiennes, ou autres, et poursuivent leur évolution culturelle, se définit plus aussi facilement qu’avant. Approche Ainsi, ma thèse explore la subjectivité hybride comme position des tensions et/ou des relations créatrices entre les cultures et les langues. Quoique je ne souhaite aucunement simplifier ni le processus, ni les questions de l’auto-identification, il m’apparaît que la subjectivité hybride est aujourd’hui une réalité croissante dans l’arène généralisée de la culture. Ce processus d’échange est particulièrement complexe chez les populations migrantes en conflit avec leur désir de s’intégrer dans les nouveaux espaces adoptés, c’est-à-dire leur pays d’accueil. Ce réel désir d’appartenance peut entrer en conflit avec celui de garder les espaces originels de la culture définie par son pays d’origine. Ainsi, les références antérieures de l’identification d’une personne, les fondements de son individualité, son noyau, peuvent toujours ne pas correspondre à, ou bien fonctionner harmonieusement avec, les références extérieures et les couches d’identification changeantes, celles qu’elle s’approprie du pays d’accueil. Puisque nos politiques, nos religions et nos établissements d’enseignement proviennent des représentations nationales de la culture et de la communauté, le processus d’identification et la création de son individualité extérieure sont formées par le contact avec ces établissements. La façon dont une personne va chercher l’identification entre les espaces personnels et les espaces publics détermine ainsi le degré de conflit et/ou de lien créatif éprouvé entre les modes et les codes des espaces culturels et linguistiques. Par conséquent, l’identification des populations migrantes suggère que la « community and culture will represent both a hybridization of home and host cultures » (Straubhaar 27). Il y a beaucoup d’écrits au sujet de l’hybridité et des questions de l’identité et de la patrie, toutefois cette thèse aborde la valeur créative de l’alternance de codes culturels et linguistiques. Ce que la littérature indiquera Par conséquent, la plate-forme à partir de laquelle j’explore mon sujet de l’hybridité flotte entre l’interprétation postcoloniale de Homi Bhabha concernant le troisième espace hybride; le modèle d’hétéroglossie de Mikhail Bakhtine qui englobent plusieurs de mes exemples; la représentation de Roland Barthes sur l’identité comme espace transgressif qui est un modèle de référence et la contribution de Chantal Zabus sur le palimpseste et l’alternance de codes africains. J’utilise aussi le modèle de Sherry Simon portant sur l’espace urbain hybride de Montréal qui établit un lien important avec la valeur des échanges culturels et linguistiques, et les analyses de Janet Paterson. En effet, la façon dont elle traite la figure de l’Autre dans les modèles littéraires au Québec fournisse un aperçu régional et national de l’identification hybride. Enfin, l’exploration du bilinguisme de Doris Sommer comme espace esthétique et même humoristique d’identification situe l’hybridité dans une espace de rencontre créative. Conséquence Mon approche dans cette thèse ne prétend pas résoudre les problèmes qui peuvent résulter des plates-formes de la subjectivité hybride. Pour cette raison, j’évite d’aborder toute approche politique ou nationaliste de l’identité qui réfute l’identification hybride. De la même façon, je n’amène pas de discussion approfondie sur les questions postcoloniales. Le but de cette thèse est de démontrer à quel point la subjectivité hybride peut être une zone de relation créatrice lorsque l’alternance de codes permet des échanges de communication plus intimes entre les cultures et les langues. C’est un espace qui devient créateur parce qu’il favorise une attitude plus ouverte vis-à-vis les différents champs qui passent par la culture, aussi bien la langue, que la sexualité, la politique ou la religion. Les zones hybrides de l’identification nous permettent de contester les traditions dépassées, les coutumes, les modes de communication et la non-acceptation, toutes choses dépassées qui emprisonnent le désir et empêchent d’explorer et d’adopter des codes en dehors des normes et des modèles de la culture contenus dans le discours blanc, dominant, de l’appartenance culturelle et linguistique mondialisée. Ainsi, il appert que ces zones des relations multi-ethniques exigent plus d’attention des cercles scolaires puisque la population des centres urbains à travers l’Amérique du Nord devient de plus en plus nourrie par d’autres types de populations. Donc, il existe un besoin réel d’établir une communication sincère qui permettrait à la population de bien comprendre les populations adoptées. C’est une invitation à stimuler une relation plus intime de l’un avec l’autre. Toutefois, il est évident qu’une communication efficace à travers les frontières des codes linguistiques, culturels, sexuels, religieux et politiques exige une négociation continuelle. Mais une telle négociation peut stimuler la compréhension plus juste des différences (culturelle ou linguistique) si des institutions académiques offrent des programmes d’études intégrant davantage les littératures migrantes. Ma thèse vise à illustrer (par son choix littéraire) l’identification hybride comme une réalité importante dans les cultures généralisées qui croissent toujours aujourd’hui. Les espaces géographiques nous gardent éloignés les uns des autres, mais notre consommation de produits exotiques, qu’ils soient culturels ou non, et même notre consommation de l’autre, s’est rétrécie sensiblement depuis les deux dernières décennies et les indicateurs suggèrent que ce processus n’est pas une tendance, mais plutôt une nouvelle manière d’éprouver la vie et de connaître les autres. Ainsi les marqueurs qui forment nos frontières externes, aussi bien que ces marqueurs qui nous définissent de l’intérieur, exigent un examen minutieux de ces enjeux inter(trans)culturels, surtout si nous souhaitons nous en tenir avec succès à des langues et des codes culturels présents, tout en favorisant la diversité culturelle et linguistique. MOTS-CLÉS : identification hybride, mouvement ouvert, alternance de code linguistique, négociation des espaces, tensions, connectivité créative

Improving automation in model-driven engineering using examples

Cette thèse a pour but d’améliorer l’automatisation dans l’ingénierie dirigée par les modèles (MDE pour Model Driven Engineering). MDE est un paradigme qui promet de réduire la complexité du logiciel par l’utilisation intensive de modèles et des transformations automatiques entre modèles (TM). D’une façon simplifiée, dans la vision du MDE, les spécialistes utilisent plusieurs modèles pour représenter un logiciel, et ils produisent le code source en transformant automatiquement ces modèles. Conséquemment, l’automatisation est un facteur clé et un principe fondateur de MDE. En plus des TM, d’autres activités ont besoin d’automatisation, e.g. la définition des langages de modélisation et la migration de logiciels. Dans ce contexte, la contribution principale de cette thèse est de proposer une approche générale pour améliorer l’automatisation du MDE. Notre approche est basée sur la recherche méta-heuristique guidée par les exemples. Nous appliquons cette approche sur deux problèmes importants de MDE, (1) la transformation des modèles et (2) la définition précise de langages de modélisation. Pour le premier problème, nous distinguons entre la transformation dans le contexte de la migration et les transformations générales entre modèles. Dans le cas de la migration, nous proposons une méthode de regroupement logiciel (Software Clustering) basée sur une méta-heuristique guidée par des exemples de regroupement. De la même façon, pour les transformations générales, nous apprenons des transformations entre modèles en utilisant un algorithme de programmation génétique qui s’inspire des exemples des transformations passées. Pour la définition précise de langages de modélisation, nous proposons une méthode basée sur une recherche méta-heuristique, qui dérive des règles de bonne formation pour les méta-modèles, avec l’objectif de bien discriminer entre modèles valides et invalides. Les études empiriques que nous avons menées, montrent que les approches proposées obtiennent des bons résultats tant quantitatifs que qualitatifs. Ceux-ci nous permettent de conclure que l’amélioration de l’automatisation du MDE en utilisant des méthodes de recherche méta-heuristique et des exemples peut contribuer à l’adoption plus large de MDE dans l’industrie à là venir.

Abitbol : un langage sur mesure pour la métaprogrammation

Ce mémoire a pour thèse que les fonctions devraient être transparentes lors de la phase de métaprogrammation. En effet, la métaprogrammation se veut une possibilité pour le programmeur d’étendre le compilateur. Or, dans un style de programmation fonctionnelle, la logique du programme se retrouve dans les définitions des diverses fonctions le composant. Puisque les fonctions sont généralement opaques, l’impossibilité d’accéder à cette logique limite les applications possibles de la phase de métaprogrammation. Nous allons illustrer les avantages que procurent les fonctions transparentes pour la métaprogrammation. Nous donnerons notamment l’exemple du calcul symbolique et un exemple de nouvelles optimisations désormais possibles. Nous illustrerons également que la transparence des fonctions permet de faire le pont entre les datatypes du programme et les fonctions. Nous allons également étudier ce qu'implique la présence de fonctions transparentes au sein d'un langage. Nous nous concentrerons sur les aspects reliés à l'implantation de ces dernières, aux performances et à la facilité d'utilisation. Nous illustrerons nos propos avec le langage Abitbol, un langage créé sur mesure pour la métaprogrammation.

Studies on a syntax based approach for translation between structurally different languages and the development of a prototype for Malayalam to English translation

This thesis summarizes the results on the studies on a syntax based approach for translation between Malayalam, one of Dravidian languages and English and also on the development of the major modules in building a prototype machine translation system from Malayalam to English. The development of the system is a pioneering effort in Malayalam language unattempted by previous researchers. The computational models chosen for the system is first of its kind for Malayalam language. An in depth study has been carried out in the design of the computational models and data structures needed for different modules: morphological analyzer , a parser, a syntactic structure transfer module and target language sentence generator required for the prototype system. The generation of list of part of speech tags, chunk tags and the hierarchical dependencies among the chunks required for the translation process also has been done. In the development process, the major goals are: (a) accuracy of translation (b) speed and (c) space. Accuracy-wise, smart tools for handling transfer grammar and translation standards including equivalent words, expressions, phrases and styles in the target language are to be developed. The grammar should be optimized with a view to obtaining a single correct parse and hence a single translated output. Speed-wise, innovative use of corpus analysis, efficient parsing algorithm, design of efficient Data Structure and run-time frequency-based rearrangement of the grammar which substantially reduces the parsing and generation time are required. The space requirement also has to be minimised

HWR for Indian Languages: A Comprehensive Survey

Few major Research works are going in the field of Handwriting Word Recognition (HWR) of Indian languages. This paper surveys the major works of offline/online handwritten word recognition. Techniques involved in word recognition are also discussed. Major works carried out in Bangla, Urdu, Tamil and Hindi are mentioned in this paper. Advancement towards HWR in other Indian languages are also discussed. Application of offline HWR is also discussed

Design and Programming of Cathodic Protection for SHIPS

In order to minimize the risk of failures or major renewals of hull structures during the ship's expected life span, it is imperative that the precaution must be taken with regard to an adequate margin of safety against any one or combination of failure modes including excessive yielding, buckling, brittle fracture, fatigue and corrosion. The most efficient system for combating underwater corrosion is 'cathodic protection'. The basic principle of this method is that the ship's structure is made cathodic, i.e. the anodic (corrosion) reactions are suppressed by the application of an opposing current and the ship is there by protected. This paper deals with state of art in cathodic protection and its programming in ship structure

Evaluating the state of the art of parallel programming systems

This paper describes our plans to evaluate the present state of affairs concerning parallel programming and its systems. Three subprojects are proposed: a survey among programmers and scientists, a comparison of parallel programming systems using a standard set of test programs, and a wiki resource for the parallel programming community - the Parawiki. We would like to invite you to participate and turn these subprojects into true community efforts.

Safe Distributed Coordination of Heterogeneous Robots through Dynamic Simple Temporal Networks

Research on autonomous intelligent systems has focused on how robots can robustly carry out missions in uncertain and harsh environments with very little or no human intervention. Robotic execution languages such as RAPs, ESL, and TDL improve robustness by managing functionally redundant procedures for achieving goals. The model-based programming approach extends this by guaranteeing correctness of execution through pre-planning of non-deterministic timed threads of activities. Executing model-based programs effectively on distributed autonomous platforms requires distributing this pre-planning process. This thesis presents a distributed planner for modelbased programs whose planning and execution is distributed among agents with widely varying levels of processor power and memory resources. We make two key contributions. First, we reformulate a model-based program, which describes cooperative activities, into a hierarchical dynamic simple temporal network. This enables efficient distributed coordination of robots and supports deployment on heterogeneous robots. Second, we introduce a distributed temporal planner, called DTP, which solves hierarchical dynamic simple temporal networks with the assistance of the distributed Bellman-Ford shortest path algorithm. The implementation of DTP has been demonstrated successfully on a wide range of randomly generated examples and on a pursuer-evader challenge problem in simulation.

Building Grounded Abstractions for Artificial Intelligence Programming

Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach suffers from particular drawbacks. High-level AI uses abstractions that often have no relation to the way real, biological brains work. Low-level AI, on the other hand, tends to lack the powerful abstractions that are needed to express complex structures and relationships. I have tried to combine the best features of both approaches, by building a set of programming abstractions defined in terms of simple, biologically plausible components. At the ``ground level'', I define a primitive, perceptron-like computational unit. I then show how more abstract computational units may be implemented in terms of the primitive units, and show the utility of the abstract units in sample networks. The new units make it possible to build networks using concepts such as long-term memories, short-term memories, and frames. As a demonstration of these abstractions, I have implemented a simulator for ``creatures'' controlled by a network of abstract units. The creatures exist in a simple 2D world, and exhibit behaviors such as catching mobile prey and sorting colored blocks into matching boxes. This program demonstrates that it is possible to build systems that can interact effectively with a dynamic physical environment, yet use symbolic representations to control aspects of their behavior.

On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(lambda) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(lambda) and Q-learning belong.

Reasoning about Temporal Context using Ontology and Abductive Constraint Logic Programming

The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.

Reasoning about Temporal Context using Ontology and Abductive Constraint Logic Programming

The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.

Reasoning about Temporal Context using Ontology and Abductive Constraint Logic Programming

The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.

Reasoning about Temporal Context using Ontology and Abductive Constraint Logic Programming

The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.