Parallel nonconvex generalized Benders decomposition for natural gas production network planning under uncertainty

A scenario-based two-stage stochastic programming model for gas production network planning under uncertainty is usually a large-scale nonconvex mixed-integer nonlinear programme (MINLP), which can be efficiently solved to global optimality with nonconvex generalized Benders decomposition (NGBD). This paper is concerned with the parallelization of NGBD to exploit multiple available computing resources. Three parallelization strategies are proposed, namely, naive scenario parallelization, adaptive scenario parallelization, and adaptive scenario and bounding parallelization. Case study of two industrial natural gas production network planning problems shows that, while the NGBD without parallelization is already faster than a state-of-the-art global optimization solver by an order of magnitude, the parallelization can improve the efficiency by several times on computers with multicore processors. The adaptive scenario and bounding parallelization achieves the best overall performance among the three proposed parallelization strategies.

Automatically Evolving Rotation-invariant Texture Image Descriptors by Genetic Programming

In computer vision, training a model that performs classification effectively is highly dependent on the extracted features, and the number of training instances. Conventionally, feature detection and extraction are performed by a domain-expert who, in many cases, is expensive to employ and hard to find. Therefore, image descriptors have emerged to automate these tasks. However, designing an image descriptor still requires domain-expert intervention. Moreover, the majority of machine learning algorithms require a large number of training examples to perform well. However, labelled data is not always available or easy to acquire, and dealing with a large dataset can dramatically slow down the training process. In this paper, we propose a novel Genetic Programming based method that automatically synthesises a descriptor using only two training instances per class. The proposed method combines arithmetic operators to evolve a model that takes an image and generates a feature vector. The performance of the proposed method is assessed using six datasets for texture classification with different degrees of rotation, and is compared with seven domain-expert designed descriptors. The results show that the proposed method is robust to rotation, and has significantly outperformed, or achieved a comparable performance to, the baseline methods.

From Kandinsky to Java (The Use of 20th Century Abstract Art in Learning Programming)

At the University of Worcester we are continually striving to find new approaches to the learning and teaching of programming, to improve the quality of learning and the student experience. Over the past three years we have used the contexts of robotics, computer games, and most recently a study of Abstract Art to this end. This paper discusses our motivation for using Abstract Art as a context, details our principles and methodology, and reports on an evaluation of the student experience. Our basic tenet is that one can view the works of artists such as Kandinsky, Klee and Malevich as Object-Oriented (OO) constructions. Discussion of these works can therefore be used to introduce OO principles, to explore the meaning of classes, methods and attributes and finally to synthesize new works of art through Java code. This research has been conducted during delivery of an ���Advanced OOP (Java)��� programming module at final-year Undergraduate level, and during a Masters��� OO-Programming (Java) module. This allows a comparative evaluation of novice and experienced programmers��� learning. In this paper, we identify several instructional factors which emerge from our approach, and reflect upon the associated pedagogy. A Catalogue of ArtApplets is provided at the associated web-site.

A parallel method for solving pentadiagonal systems of linear equations

A new parallel approach for solving a pentadiagonal linear system is presented. The parallel partition method for this system and the TW parallel partition method on a chain of P processors are introduced and discussed. The result of this algorithm is a reduced pentadiagonal linear system of order P \Gamma 2 compared with a system of order 2P \Gamma 2 for the parallel partition method. More importantly the new method involves only half the number of communications startups than the parallel partition method (and other standard parallel methods) and hence is a far more efficient parallel algorithm.

A fast parallel hyperspectral coded aperture algorithm for compressive sensing using OpenCL

In this paper, we develop a fast implementation of an hyperspectral coded aperture (HYCA) algorithm on different platforms using OpenCL, an open standard for parallel programing on heterogeneous systems, which includes a wide variety of devices, from dense multicore systems from major manufactures such as Intel or ARM to new accelerators such as graphics processing units (GPUs), field programmable gate arrays (FPGAs), the Intel Xeon Phi and other custom devices. Our proposed implementation of HYCA significantly reduces its computational cost. Our experiments have been conducted using simulated data and reveal considerable acceleration factors. This kind of implementations with the same descriptive language on different architectures are very important in order to really calibrate the possibility of using heterogeneous platforms for efficient hyperspectral imaging processing in real remote sensing missions.

A generic strategy for dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes

A large class of computational problems are characterised by frequent synchronisation, and computational requirements which change as a function of time. When such a problem is solved on a message passing multiprocessor machine [5], the combination of these characteristics leads to system performance which deteriorate in time. As the communication performance of parallel hardware steadily improves so load balance becomes a dominant factor in obtaining high parallel efficiency. Performance can be improved with periodic redistribution of computational load; however, redistribution can sometimes be very costly. We study the issue of deciding when to invoke a global load re-balancing mechanism. Such a decision policy must actively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. This paper discusses a generic strategy for Dynamic Load Balancing (DLB) in unstructured mesh computational mechanics applications. The strategy is intended to handle varying levels of load changes throughout the run. The major issues involved in a generic dynamic load balancing scheme will be investigated together with techniques to automate the implementation of a dynamic load balancing mechanism within the Computer Aided Parallelisation Tools (CAPTools) environment, which is a semi-automatic tool for parallelisation of mesh based FORTRAN codes.

Computer aided parallelisation of unstructured mesh codes

Abstract not available

Separate compilation of structured documents

This paper draws a parallel between document preparation and the traditional processes of compilation and link editing for computer programs. A block-based document model is described which allows for separate compilation of various portions of a document. These portions are brought together and merged by a linker program, called dlink, whose pilot implementation is based on ditroff and on its underlying intermediate code. In the light of experiences with dlink the requirements for a universal object-module language for documents are discussed. These requirements often resemble the characteristics of the intermediate codes used by programming-language compilers but with interesting extra constraints which arise from the way documents are executed .

Student attitudes to plagiarism and collusion within computer science

There is a widespread perception among staff in Computer Science that plagiarism is a major problem particularly in the form of collusion in programming exercises. While departments often make use of electronic detection measures, the time consumed prosecuting plagiarism offences remains a problem. As a result departments continue to seek ways to reduce the amount of plagiarism and collusion that occurs. This paper reports the findings of a questionnaire based study which attempted to assess the students' attitudes to the issues involved in the hope that such an understanding might result in practical measures for minimizing the problem. The study revealed that while students did understand the definition of plagiarism in its most extreme cases they were often confused about less clear-cut situations. Changes in the previous experience of incoming students meeting modules originally designed on the assumption that students already had some programming background and were equipped for self-directed study would also appear to be a contributory factor in the extent of collusion in programming exercises.

Visual programming in a heterogeneous multi-core environment

�� do conhecimento geral de que, hoje em dia, a tecnologia evolui rapidamente. S��o criadas novas arquitecturas para resolver determinadas limita����es ou problemas. Por vezes, essa evolu����o �� pac��fica e n��o requer necessidade de adapta����o e, por outras, essa evolu����o pode Implicar mudan��as. As linguagens de programa����o s��o, desde sempre, o principal elo de comunica����o entre o programador e o computador. Novas linguagens continuam a aparecer e outras est��o sempre em desenvolvimento para se adaptarem a novos conceitos e paradigmas. Isto requer um esfor��o extra para o programador, que tem de estar sempre atento a estas mudan��as. A Programa����o Visual pode ser uma solu����o para este problema. Exprimir fun����es como m��dulos que recebem determinado Input e retomam determinado output poder�� ajudar os programadores espalhados pelo mundo, atrav��s da possibilidade de lhes dar uma margem para se abstra��rem de pormenores de baixo n��vel relacionados com uma arquitectura espec��fica. Esta tese n��o s�� mostra como combinar as capacidades do CeII/B.E. (que tem uma arquitectura multi��processador heterog��nea) com o OpenDX (que tem um ambiente de programa����o visual), como tamb��m demonstra que tal pode ser feito sem grande perda de performance. ABSTRACT; lt is known that nowadays technology develops really fast. New architectures are created ln order to provide new solutions for different technology limitations and problems. Sometimes, this evolution is pacific and there is no need to adapt to new technologies, but things also may require a change every once ln a while. Programming languages have always been the communication bridge between the programmer and the computer. New ones keep coming and other ones keep improving ln order to adapt to new concepts and paradigms. This requires an extra-effort for the programmer, who always needs to be aware of these changes. Visual Programming may be a solution to this problem. Expressing functions as module boxes which receive determined Input and return determined output may help programmers across the world by giving them the possibility to abstract from specific low-level hardware issues. This thesis not only shows how the CeII/B.E. (which has a heterogeneous multi-core architecture) capabilities can be combined with OpenDX (which has a visual programming environment), but also demonstrates that lt can be done without losing much performance.

Embedding sustainability into the new computer science curriculum for English schools

The primary goals of this study are to: embed sustainable concepts of energy consumption into certain part of existing Computer Science curriculum for English schools; investigate how to motivate 7-to-11 years old kids to learn these concepts; promote responsive ICT (Information and Communications Technology) use by these kids in their daily life; raise their awareness of today���s ecological challenges. Sustainability-related ICT lessons developed aim to provoke computational thinking and creativity to foster understanding of environmental impact of ICT and positive environmental impact of small changes in user energy consumption behaviour. The importance of including sustainability into the Computer Science curriculum is due to the fact that ICT is both a solution and one of the causes of current world ecological problems. This research follows Agile software development methodology. In order to achieve the aforementioned goals, sustainability requirements, curriculum requirements and technical requirements are firstly analysed. Secondly, the web-based user interface is designed. In parallel, a set of three online lessons (video, slideshow and game) is created for the website GreenICTKids.com taking into account several green design patterns. Finally, the evaluation phase involves the collection of adults��� and kids��� feedback on the following: user interface; contents; user interaction; impacts on the kids��� sustainability awareness and on the kids��� behaviour with technologies. In conclusion, a list of research outcomes is as follows: 92% of the adults learnt more about energy consumption; 80% of the kids are motivated to learn about energy consumption and found the website easy to use; 100% of the kids understood the contents and liked website���s visual aspect; 100% of the kids will try to apply in their daily life what they learnt through the online lessons.

Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Integer Linear Programming for Sequence Problems: A general approach to reduce the problem size

Sequence problems belong to the most challenging interdisciplinary topics of the actuality. They are ubiquitous in science and daily life and occur, for example, in form of DNA sequences encoding all information of an organism, as a text (natural or formal) or in form of a computer program. Therefore, sequence problems occur in many variations in computational biology (drug development), coding theory, data compression, quantitative and computational linguistics (e.g. machine translation). In recent years appeared some proposals to formulate sequence problems like the closest string problem (CSP) and the farthest string problem (FSP) as an Integer Linear Programming Problem (ILPP). In the present talk we present a general novel approach to reduce the size of the ILPP by grouping isomorphous columns of the string matrix together. The approach is of practical use, since the solution of sequence problems is very time consuming, in particular when the sequences are long.

Factors influencing success in introductory programming courses.

This study looked at the reasons why Vanier College students in computer programming are encountering difficulties in their learning process, Factors such as prior academic background, prior computer experience, mother tongue, and learning styles were examined to see how they play a role in students' success in programming courses. The initial research hypotheses were the following : Computer science students using understanding and integrating succeed better than students using following coding, or problem solving. Students using problem solving succeed better than those who use participating and enculturation. Students who use coding perform better than those who prefer participating ans enculturation. In addition, this study hoped to examine whether there is a gender difference in how students learn programming.||R��sum�� :||La pr��sente ��tude a examin�� les raisons pour lesquelles les ��tudiants en informatique du Coll��ge Vanier rencontrent des difficult��s dans leurs ��tudes en programmation. Les facteurs tel que le niveau des ��tudes pr��c��dentes, l'exp��rience en informatique, la langue maternelle e les m��thodes d'apprentissage ont ��t�� consid��r��s pour voir quel r��le ces facteurs jouent pour promouvoir la r��ussite dans les cours de programmation.Les hypoth��ses initiales de recherche ont ��t�� formul��es comme suit : 1. Les ��tudiants en informatique utilisant la compr��hension et l'int��gration r��ussissent mieux que ceux utilisant ��suivre��, le codage ou la r��solution des probl��mes. 2, Les ��tudiants utilisant la r��solution des probl��mes r��ussissent mieux que ceux qui utilisent la participation dans la culture informatique. 3, Les ��tudiants utilisant le codage r��ussissent mieux que ceux qui utilisent la participation dans la culture informatique.