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.

Ethnic Identity and School Ambition : the Case of Second Generation Youth from a Latin-American Background in Montreal

Ce mémoire propose d’étudier l’articulation entre l’identité ethnique (à l’adolescence) et l’ambition scolaire – ici définie comme l’ensemble des motivations, des moyens de persévérance et du niveau scolaire – notamment à travers les concepts d’assimilation et de la résistance culturelle (McAndrew 2008). Nous nous intéressons aux jeunes issus de l’immigration latino-américaine à Montréal. Il s’agit d’une analyse qualitative, plus précisément d’analyse de discours qui nous a permis de comprendre comment leurs expériences et leurs représentations des Latinos et des Québécois influencent leur identification ethnique ainsi que leurs perceptions et décisions en milieu scolaire. Les résultats de cette étude démontrent que l’identification ethnique, en corrélation avec le statut socio-économique et le genre, semble être liée à l’ambition scolaire. Malgré une certaine confirmation de la relation classique entre statut socio-économique et niveau de scolarité, les discours des participants ont permis de faire ressortir une particularité ethnique susceptible de contribuer à expliquer le choix de continuer aux études supérieures. Cet impact est plus important chez les jeunes femmes de notre échantillon; celles avec le niveau de scolarité le moins élevé, ont un statut socio-économique moindre et s’identifient davantage à la culture latino, en contraste avec celles les plus éduquées ayant aussi un statut socio-économique supérieur et qui s’identifiaient davantage à la culture québécoise.

Insights from youth workers regarding young people's engagement in out-of-school-time youth development programs

L’objectif de cette étude exploratoire était de mieux comprendre, du point de vue des animateurs/animatrices qui oeuvrent auprès des jeunes, le phénomène de l’engagement des jeunes dans les programmes parascolaires. Des entretiens qualitatifs ont été entrepris à cette fin avec six animateur(trices). Plusieurs obstacles à l’engagement ont été identifiés, la plupart étant extérieurs aux jeunes. Quelques actions et attitudes spécifiques des animateur(trices) ont été relevées comme importantes pour aider les jeunes à surmonter ces obstacles. De plus, la structure et le contenu du programme, ainsi que l’environnement de groupe, jouent des rôles primordiaux. Les dimensions soulevées par les animateur(trices) ont permis d’enrichir et rendre plus holistique un modèle d’engagement qui a été développé à partir d’une recension des écrits dans ce domaine. Finalement, les implications pour la formation des animateurs(trices) et pour la structure des programmes pour les jeunes ont été explorées.

Growing Up in Exile : An Ethnography of Somali Youth Raised in Kakuma Refugee Camp, Kenya

La violence chronique qui caractérise la Somalie depuis plus de deux décennies a forcé près de deux millions de personnes à fuir. Cette ethnographie étudie l’expérience de l’asile prolongé de jeunes Somaliens qui ont grandi au camp de Kakuma, au Kenya. Leur expérience est hors du commun, bien qu’un nombre croissant de réfugiés passent de longues années dans des camps pourtant conçus comme temporaires, en vertu de la durée des conflits et de la normalisation de pratiques de mise à l’écart de populations « indésirables ». Nous explorons la perception qu’ont ces jeunes de leur environnement et de quelle façon leur exil structure leur perception du passé et de leur pays d’origine, et de leur futur. Ce faisant, nous considérons à la fois les spécificités du contexte et l’environnement global, afin de comprendre comment l’expérience des gens est façonnée par (et façonne) les dynamiques sociales, politiques, économiques et historiques. Nous observons que le camp est, et demeure, un espace de confinement, indépendamment de sa durée d’existence ; bien que conçu comme un lieu de gestion rationnelle des populations, le camp devient un monde social où se développent de nouvelles pratiques ; les jeunes Somaliens font preuve d’agentivité et interprètent leur expérience de manière à rendre leur quotidien acceptable ; ces derniers expriment une frustration croissante lorsque leurs études sont terminées et qu’ils peinent à s’établir en tant qu’adultes, ce qui exacerbe leur désir de quitter le camp. En effet, même s’il existe depuis plus de 20 ans, le camp demeure un lieu de transition. L’expérience de jeunes Somaliens qui ont grandi dans un camp de réfugiés n’a pas été étudiée auparavant. Nous soutenons que cette expérience est caractérisée par des tensions entre contraintes et opportunités, mobilité et immobilité, isolation et connexion ou victimisation et affirmation du sujet – et des temporalités contradictoires. Cette étude souligne que des notions comme la convivialité ou la pluralité des appartenances développées dans la littérature sur la cohabitation interethnique dans les villes ou sur l’identité des migrants aident à appréhender le réalité du camp. Cette ethnographie montre également que, loin d’être des victimes passives, les réfugiés contribuent à trouver des solutions à leur exil.

Differences in Standing and Sitting Postures of Youth with Idiopathic Scoliosis from Quantitative Analysis of Digital Photographs

The objective of this study was to explore whether differences in standing and sitting postures of youth with idiopathic scoliosis could be detected from quantitative analysis of digital photographs. Standing and sitting postures of 50 participants aged 10–20-years-old with idiopathic scoliosis (Cobb angle: 15° to 60°) were assessed from digital photographs using a posture evaluation software program. Based on the XY coordinates of markers, 13 angular and linear posture indices were calculated in both positions. Paired t-tests were used to compare values of standing and sitting posture indices. Significant differences between standing and sitting positions (p < 0.05) were found for head protraction, shoulder elevation, scapula asymmetry, trunk list, scoliosis angle, waist angles, and frontal and sagittal plane pelvic tilt. Quantitative analysis of digital photographs is a clinically feasible method to measure standing and sitting postures among youth with scoliosis and to assist in decisions on therapeutic interventions.

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.

Observations on the Publicity and Usage of Parallel Programming Systems and Languages: A Survey Approach

In this publication, we report on an online survey that was carried out among parallel programmers. More than 250 people worldwide have submitted answers to our questions, and their responses are analyzed here. Although not statistically sound, the data we provide give useful insights about which parallel programming systems and languages are known and in actual use. For instance, the collected data indicate that for our survey group MPI and (to a lesser extent) C are the most widely used parallel programming system and language, respectively.

Genetic Programming meets Model-Driven Development

Genetic programming is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. In such cases it is most likely a hardwired module of a design framework that assists the engineer to optimize specific aspects of the system to be developed. It provides its results in a fixed format through an internal interface. In this paper we show how the utility of genetic programming can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our genetic programming framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools which in turn posses code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how genetic programming can be combined with model-driven development. This example clearly illustrates the advantages of our approach – the generation of source code in different programming languages.

A User-Centric Perspective on Parallel Programming with Focus on OpenMP

The process of developing software that takes advantage of multiple processors is commonly referred to as parallel programming. For various reasons, this process is much harder than the sequential case. For decades, parallel programming has been a problem for a small niche only: engineers working on parallelizing mostly numerical applications in High Performance Computing. This has changed with the advent of multi-core processors in mainstream computer architectures. Parallel programming in our days becomes a problem for a much larger group of developers. The main objective of this thesis was to find ways to make parallel programming easier for them. Different aims were identified in order to reach the objective: research the state of the art of parallel programming today, improve the education of software developers about the topic, and provide programmers with powerful abstractions to make their work easier. To reach these aims, several key steps were taken. To start with, a survey was conducted among parallel programmers to find out about the state of the art. More than 250 people participated, yielding results about the parallel programming systems and languages in use, as well as about common problems with these systems. Furthermore, a study was conducted in university classes on parallel programming. It resulted in a list of frequently made mistakes that were analyzed and used to create a programmers' checklist to avoid them in the future. For programmers' education, an online resource was setup to collect experiences and knowledge in the field of parallel programming - called the Parawiki. Another key step in this direction was the creation of the Thinking Parallel weblog, where more than 50.000 readers to date have read essays on the topic. For the third aim (powerful abstractions), it was decided to concentrate on one parallel programming system: OpenMP. Its ease of use and high level of abstraction were the most important reasons for this decision. Two different research directions were pursued. The first one resulted in a parallel library called AthenaMP. It contains so-called generic components, derived from design patterns for parallel programming. These include functionality to enhance the locks provided by OpenMP, to perform operations on large amounts of data (data-parallel programming), and to enable the implementation of irregular algorithms using task pools. AthenaMP itself serves a triple role: the components are well-documented and can be used directly in programs, it enables developers to study the source code and learn from it, and it is possible for compiler writers to use it as a testing ground for their OpenMP compilers. The second research direction was targeted at changing the OpenMP specification to make the system more powerful. The main contributions here were a proposal to enable thread-cancellation and a proposal to avoid busy waiting. Both were implemented in a research compiler, shown to be useful in example applications, and proposed to the OpenMP Language Committee.

Evolving Distributed Algorithms with Genetic Programming

Distributed systems are one of the most vital components of the economy. The most prominent example is probably the internet, a constituent element of our knowledge society. During the recent years, the number of novel network types has steadily increased. Amongst others, sensor networks, distributed systems composed of tiny computational devices with scarce resources, have emerged. The further development and heterogeneous connection of such systems imposes new requirements on the software development process. Mobile and wireless networks, for instance, have to organize themselves autonomously and must be able to react to changes in the environment and to failing nodes alike. Researching new approaches for the design of distributed algorithms may lead to methods with which these requirements can be met efficiently. In this thesis, one such method is developed, tested, and discussed in respect of its practical utility. Our new design approach for distributed algorithms is based on Genetic Programming, a member of the family of evolutionary algorithms. Evolutionary algorithms are metaheuristic optimization methods which copy principles from natural evolution. They use a population of solution candidates which they try to refine step by step in order to attain optimal values for predefined objective functions. The synthesis of an algorithm with our approach starts with an analysis step in which the wanted global behavior of the distributed system is specified. From this specification, objective functions are derived which steer a Genetic Programming process where the solution candidates are distributed programs. The objective functions rate how close these programs approximate the goal behavior in multiple randomized network simulations. The evolutionary process step by step selects the most promising solution candidates and modifies and combines them with mutation and crossover operators. This way, a description of the global behavior of a distributed system is translated automatically to programs which, if executed locally on the nodes of the system, exhibit this behavior. In our work, we test six different ways for representing distributed programs, comprising adaptations and extensions of well-known Genetic Programming methods (SGP, eSGP, and LGP), one bio-inspired approach (Fraglets), and two new program representations called Rule-based Genetic Programming (RBGP, eRBGP) designed by us. We breed programs in these representations for three well-known example problems in distributed systems: election algorithms, the distributed mutual exclusion at a critical section, and the distributed computation of the greatest common divisor of a set of numbers. Synthesizing distributed programs the evolutionary way does not necessarily lead to the envisaged results. In a detailed analysis, we discuss the problematic features which make this form of Genetic Programming particularly hard. The two Rule-based Genetic Programming approaches have been developed especially in order to mitigate these difficulties. In our experiments, at least one of them (eRBGP) turned out to be a very efficient approach and in most cases, was superior to the other representations.

AFL-1: A Programming Language for Massively Concurrent Computers

Computational models are arising is which programs are constructed by specifying large networks of very simple computational devices. Although such models can potentially make use of a massive amount of concurrency, their usefulness as a programming model for the design of complex systems will ultimately be decided by the ease in which such networks can be programmed (constructed). This thesis outlines a language for specifying computational networks. The language (AFL-1) consists of a set of primitives, ad a mechanism to group these elements into higher level structures. An implementation of this language runs on the Thinking Machines Corporation, Connection machine. Two significant examples were programmed in the language, an expert system (CIS), and a planning system (AFPLAN). These systems are explained and analyzed in terms of how they compare with similar systems written in conventional languages.

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.