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.

Game Design & Programming: progettazione e sviluppo di un videogioco 3D con Unity

Questa Tesi prende in esame tutte le fasi che portano alla realizzazione di un generico videogioco applicandole per creare, dal principio, un gioco 3D con Unity. Se ne analizzerà l'ideazione, la progettazione degli ambienti ma anche degli algoritmi implementati, la produzione e quindi la scrittura del codice per poi terminare con i test effettuati.

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.

Evolution of classifiers for pitch estimation of piano music using cartesian genetic programming

Pitch Estimation, also known as Fundamental Frequency (F0) estimation, has been a popular research topic for many years, and is still investigated nowadays. The goal of Pitch Estimation is to find the pitch or fundamental frequency of a digital recording of a speech or musical notes. It plays an important role, because it is the key to identify which notes are being played and at what time. Pitch Estimation of real instruments is a very hard task to address. Each instrument has its own physical characteristics, which reflects in different spectral characteristics. Furthermore, the recording conditions can vary from studio to studio and background noises must be considered. This dissertation presents a novel approach to the problem of Pitch Estimation, using Cartesian Genetic Programming (CGP).We take advantage of evolutionary algorithms, in particular CGP, to explore and evolve complex mathematical functions that act as classifiers. These classifiers are used to identify piano notes pitches in an audio signal. To help us with the codification of the problem, we built a highly flexible CGP Toolbox, generic enough to encode different kind of programs. The encoded evolutionary algorithm is the one known as 1 + , and we can choose the value for . The toolbox is very simple to use. Settings such as the mutation probability, number of runs and generations are configurable. The cartesian representation of CGP can take multiple forms and it is able to encode function parameters. It is prepared to handle with different type of fitness functions: minimization of f(x) and maximization of f(x) and has a useful system of callbacks. We trained 61 classifiers corresponding to 61 piano notes. A training set of audio signals was used for each of the classifiers: half were signals with the same pitch as the classifier (true positive signals) and the other half were signals with different pitches (true negative signals). F-measure was used for the fitness function. Signals with the same pitch of the classifier that were correctly identified by the classifier, count as a true positives. Signals with the same pitch of the classifier that were not correctly identified by the classifier, count as a false negatives. Signals with different pitch of the classifier that were not identified by the classifier, count as a true negatives. Signals with different pitch of the classifier that were identified by the classifier, count as a false positives. Our first approach was to evolve classifiers for identifying artifical signals, created by mathematical functions: sine, sawtooth and square waves. Our function set is basically composed by filtering operations on vectors and by arithmetic operations with constants and vectors. All the classifiers correctly identified true positive signals and did not identify true negative signals. We then moved to real audio recordings. For testing the classifiers, we picked different audio signals from the ones used during the training phase. For a first approach, the obtained results were very promising, but could be improved. We have made slight changes to our approach and the number of false positives reduced 33%, compared to the first approach. We then applied the evolved classifiers to polyphonic audio signals, and the results indicate that our approach is a good starting point for addressing the problem of Pitch Estimation.

Character in Context: Informing Character Education Programming

The Positive Youth Development (PYD) perspective is a strength-based conceptualization of youth. It highlights the importance of mutually beneficial relationships between youth and their environment to develop the “Five Cs”, key assets that include character. Character has long been a subject of programming due to its focus on helping children lead moral, empathic, and prosocial lives. There are, however, many limitations in character research, including poorly operationalized definitions of character; a failure to examine the developmental and broader social context in which character exists; and a lack of evaluation of more practical character programming. The goal of this dissertation was to address these gaps in knowledge and inform the character education programming literature. The first study examined the relationships among age, gender, the school social context, and character. Moral character was negatively associated with grade, and being a girl was positively associated with moral character. The relationships between positive peer interactions at school and character (fairness, integrity) were stronger among students who reported low initial moral character when positive peer interactions was high. In the second study, the Build Character: Build Success Program, a character education program, was evaluated over six months to examine its effects on character behaviours, victimization, and school climate. No program effects were found for students in grades 1 to 3, but a slight decrease in victimization in one experimental school was found for students in grades 4 to 8. This lack of general program effects may be due to the short-term nature of the intervention, which may not have been long enough to result in measurable behaviour change. Implementation data indicated that teachers did not teach all program elements, which also may have influenced the results of the program evaluation. The present dissertation contributes to knowledge about character and its programming by: introducing new measures to operationalize character, discovering developmental patterns in character in school-aged children, highlighting gender differences in character, examining character within its broad social context, and evaluating short-term character education programming.

Code pattern analysis of object-oriented programming languages

Code patterns, including programming patterns and design patterns, are good references for programming language feature improvement and software re-engineering. However, to our knowledge, no existing research has attempted to detect code patterns based on code clone detection technology. In this study, we build upon the previous work and propose to detect and analyze code patterns from a collection of open source projects using NiPAT technology. Because design patterns are most closely associated with object-oriented languages, we choose Java and Python projects to conduct our study. The tool we use for detecting patterns is NiPAT, a pattern detecting tool originally developed for the TXL programming language based on the NiCad clone detector. We extend NiPAT for the Java and Python programming languages. Then, we try to identify all the patterns from the pattern report and classify them into several different categories. In the end of the study, we analyze all the patterns and compare the differences between Java and Python patterns.

New Rigorous Decomposition Methods for Mixed-integer Linear and Nonlinear Programming

Process systems design, operation and synthesis problems under uncertainty can readily be formulated as two-stage stochastic mixed-integer linear and nonlinear (nonconvex) programming (MILP and MINLP) problems. These problems, with a scenario based formulation, lead to large-scale MILPs/MINLPs that are well structured. The first part of the thesis proposes a new finitely convergent cross decomposition method (CD), where Benders decomposition (BD) and Dantzig-Wolfe decomposition (DWD) are combined in a unified framework to improve the solution of scenario based two-stage stochastic MILPs. This method alternates between DWD iterations and BD iterations, where DWD restricted master problems and BD primal problems yield a sequence of upper bounds, and BD relaxed master problems yield a sequence of lower bounds. A variant of CD, which includes multiple columns per iteration of DW restricted master problem and multiple cuts per iteration of BD relaxed master problem, called multicolumn-multicut CD is then developed to improve solution time. Finally, an extended cross decomposition method (ECD) for solving two-stage stochastic programs with risk constraints is proposed. In this approach, a CD approach at the first level and DWD at a second level is used to solve the original problem to optimality. ECD has a computational advantage over a bilevel decomposition strategy or solving the monolith problem using an MILP solver. The second part of the thesis develops a joint decomposition approach combining Lagrangian decomposition (LD) and generalized Benders decomposition (GBD), to efficiently solve stochastic mixed-integer nonlinear nonconvex programming problems to global optimality, without the need for explicit branch and bound search. In this approach, LD subproblems and GBD subproblems are systematically solved in a single framework. The relaxed master problem obtained from the reformulation of the original problem, is solved only when necessary. A convexification of the relaxed master problem and a domain reduction procedure are integrated into the decomposition framework to improve solution efficiency. Using case studies taken from renewable resource and fossil-fuel based application in process systems engineering, it can be seen that these novel decomposition approaches have significant benefit over classical decomposition methods and state-of-the-art MILP/MINLP global optimization solvers.

The era of smartphones: Back to our biological makeup?

SIN FINANCIACIÓN

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.

Plan de negocios Bicigo app

La gran cantidad de personas interesadas actualmente en cuidar de su salud por medio de la Bicicleta, es una tendencia que cada vez toma más fuerza y por esto, se tomara como ventaja que la ciudad de Bogotá con sus últimos alcaldes han decidió apoyar el uso de esta. Aplicación para realizar grupos de ciclistas y poder salir cualquier día de la semana acompañado de más personas por un tema de transporte pero también de ocio. El objetivo es que las personas que no utilizan la bicicleta por miedo a salir solos, puedan unirse a diferentes grupos y hacer bici paseos por la ciudad, también contemplamos el hecho de que existen personas que quieren montar bicicleta como aficionados, es decir que salen por la carreteras aledañas a la capital pero muchas veces no tienen grupo con quien rodar. Queremos para el año 2020, lograr ser una de las aplicaciones de Bicicletas más exitosa de la ciudadanía de Bogotá, siendo una de las aplicaciones que mas apoya el uso diario y deportivo de la bicicleta. Nuestra aplicación ofrece el servicio principalmente de reunir gente y hacer paseos con diferentes personas haciendo uso de las bicicletas, dentro de la ciudad como ocio y transporte se realizarían en la mañana y noches, pero así mismo realizar grupos para hacer uso de la bicicleta por carreteras, es decir más como modo profesional o aficionado. Nuestra aplicación cuenta con una interface para seleccionar el tipo de bici usuario y segundo por donde o a donde quiere dirigirse para así mismo mostrarle las rutas cercanas a él. Nuestra característica principal es la unión de diferentes grupos, personas y entidades para hacer uso de la Bicicleta, tenemos una plataforma interactiva y fácil de usar, tan fácil que cualquier persona que no esté inmersa en el mundo de los Smartphone o aplicaciones pueda aprender a usarla. Unas de las ventajas con las que cuento es que desde muy joven me ha gustado montar en bicicletas y es así como decido crear una aplicación ya que compañeros, familiares y conocidos no salían a montar bicicleta solo conmigo, preferían que fuese un grupo más grande. Así mismo cuento con 3 compañeros de la universidad Javeriana que son programadores y ellos me van a brindar apoyo con la programación de la aplicación, y una compañera cercana a mí que estudio diseño industrial y me brindara apoyo con el diseño e imagen corporativa de la aplicación. Cuento con planta física para ubicar la oficina de nuestra empresa. Esta aplicación va dirigida principalmente a los habitantes de la ciudad de Bogotá, interesados en el cuidado de su salud combinado con medio de transporte, y personas correspondientes al estrato 2 en adelante, ya que son las personas que normalmente hacen uso de la bicicleta o que son personas potenciales para empezar hacer uso de la bicicleta. . La ciudad de Bogotá cuenta con 8’037.732 habitantes y este proyecto va ser desarrollado en toda la ciudad, toca tener en cuenta que la ciudad esta mesclada entre la diferente estratificación, no dirigimos a los estratos 2 y 3 que tenga la posibilidad de tener su Bicicleta y un celular tipo Smartphone, para los estratos 4, 5 y 6 sabemos que tiene la facilidad de obtener una bicicleta y ellos son nuestro usuario potencial el cual generaríamos un cambio y tomarían su bicicleta para hacer ejercicio como ocio y como medio de transporte. En cuanto a la proyección financiera para la aplicación, como se mencionó anteriormente, contamos con una gran ventaja, ya que la inversión requerida será menor debido a la propiedad con la que cuento para llevar a cabo el proyecto. Una propiedad de 60 metros cuadrados para empezar, la cual cuenta con salas de reunión y auditorio, un parqueaderos exteriores. Al hacer la calculación se va tener en cuenta el pago de un arriendo sin importan que sea de nuestra propiedad y así poder evidenciar realmente como es el estado financiero y no subsidiarla. Por otro lado, la inversión en efectivo que se necesitara será aproximadamente de $100.000.000 que serán $50.000.000 de mis padres y el restante saldrán de mis ahorros, Javier Amortegui Babativa, los cuales serán distribuidos para adecuación de planta, equipos y sistemas $17.616.880, para publicidad y mercadeo: $30.000.000, creación de la aplicación $34.000.000, sistemas IOS + Android $421.600, Gastos de composición empresarial y bancarios $11.000.000 y por último se va tener un provisión para imprevistos por el restante $6.961.520. Nuestras proyecciones de ventas han sido basadas en aplicaciones similares con un mismo formato de lucro con el tema de bicicletas pero no con la misma idea de negocio, nuestras proyecciones de ventas estimadas serán de $20.000.000 a $25.000.000 los primeros 3 meses, mientras tomamos fuerza en el mercado.

Constraint Programming-based Job Dispatching for Modern HPC Applications

A High-Performance Computing job dispatcher is a critical software that assigns the finite computing resources to submitted jobs. This resource assignment over time is known as the on-line job dispatching problem in HPC systems. The fact the problem is on-line means that solutions must be computed in real-time, and their required time cannot exceed some threshold to do not affect the normal system functioning. In addition, a job dispatcher must deal with a lot of uncertainty: submission times, the number of requested resources, and duration of jobs. Heuristic-based techniques have been broadly used in HPC systems, at the cost of achieving (sub-)optimal solutions in a short time. However, the scheduling and resource allocation components are separated, thus generates a decoupled decision that may cause a performance loss. Optimization-based techniques are less used for this problem, although they can significantly improve the performance of HPC systems at the expense of higher computation time. Nowadays, HPC systems are being used for modern applications, such as big data analytics and predictive model building, that employ, in general, many short jobs. However, this information is unknown at dispatching time, and job dispatchers need to process large numbers of them quickly while ensuring high Quality-of-Service (QoS) levels. Constraint Programming (CP) has been shown to be an effective approach to tackle job dispatching problems. However, state-of-the-art CP-based job dispatchers are unable to satisfy the challenges of on-line dispatching, such as generate dispatching decisions in a brief period and integrate current and past information of the housing system. Given the previous reasons, we propose CP-based dispatchers that are more suitable for HPC systems running modern applications, generating on-line dispatching decisions in a proper time and are able to make effective use of job duration predictions to improve QoS levels, especially for workloads dominated by short jobs.

Addressing challenges in heterogeneous embedded systems programming: security and performance

Embedded systems are increasingly integral to daily life, improving and facilitating the efficiency of modern Cyber-Physical Systems which provide access to sensor data, and actuators. As modern architectures become increasingly complex and heterogeneous, their optimization becomes a challenging task. Additionally, ensuring platform security is important to avoid harm to individuals and assets. This study primarily addresses challenges in contemporary Embedded Systems, focusing on platform optimization and security enforcement. The initial section of this study delves into the application of machine learning methods to efficiently determine the optimal number of cores for a parallel RISC-V cluster to minimize energy consumption using static source code analysis. Results demonstrate that automated platform configuration is not only viable but also that there is a moderate performance trade-off when relying solely on static features. The second part focuses on addressing the problem of heterogeneous device mapping, which involves assigning tasks to the most suitable computational device in a heterogeneous platform for optimal runtime. The contribution of this section lies in the introduction of novel pre-processing techniques, along with a training framework called Siamese Networks, that enhances the classification performance of DeepLLVM, an advanced approach for task mapping. Importantly, these proposed approaches are independent from the specific deep-learning model used. Finally, this research work focuses on addressing issues concerning the binary exploitation of software running in modern Embedded Systems. It proposes an architecture to implement Control-Flow Integrity in embedded platforms with a Root-of-Trust, aiming to enhance security guarantees with limited hardware modifications. The approach involves enhancing the architecture of a modern RISC-V platform for autonomous vehicles by implementing a side-channel communication mechanism that relays control-flow changes executed by the process running on the host core to the Root-of-Trust. This approach has limited impact on performance and it is effective in enhancing the security of embedded platforms.

Integrating mobile devices into a scalable Grid Computing architecture designed to perform distributed computations

The idea of Grid Computing originated in the nineties and found its concrete applications in contexts like the SETI@home project where a lot of computers (offered by volunteers) cooperated, performing distributed computations, inside the Grid environment analyzing radio signals trying to find extraterrestrial life. The Grid was composed of traditional personal computers but, with the emergence of the first mobile devices like Personal Digital Assistants (PDAs), researchers started theorizing the inclusion of mobile devices into Grid Computing; although impressive theoretical work was done, the idea was discarded due to the limitations (mainly technological) of mobile devices available at the time. Decades have passed, and now mobile devices are extremely more performant and numerous than before, leaving a great amount of resources available on mobile devices, such as smartphones and tablets, untapped. Here we propose a solution for performing distributed computations over a Grid Computing environment that utilizes both desktop and mobile devices, exploiting the resources from day-to-day mobile users that alternatively would end up unused. The work starts with an introduction on what Grid Computing is, the evolution of mobile devices, the idea of integrating such devices into the Grid and how to convince device owners to participate in the Grid. Then, the tone becomes more technical, starting with an explanation on how Grid Computing actually works, followed by the technical challenges of integrating mobile devices into the Grid. Next, the model, which constitutes the solution offered by this study, is explained, followed by a chapter regarding the realization of a prototype that proves the feasibility of distributed computations over a Grid composed by both mobile and desktop devices. To conclude future developments and ideas to improve this project are presented.

Biased Random-key Genetic Algorithms For The Winner Determination Problem In Combinatorial Auctions.

Abstract In this paper, we address the problem of picking a subset of bids in a general combinatorial auction so as to maximize the overall profit using the first-price model. This winner determination problem assumes that a single bidding round is held to determine both the winners and prices to be paid. We introduce six variants of biased random-key genetic algorithms for this problem. Three of them use a novel initialization technique that makes use of solutions of intermediate linear programming relaxations of an exact mixed integer-linear programming model as initial chromosomes of the population. An experimental evaluation compares the effectiveness of the proposed algorithms with the standard mixed linear integer programming formulation, a specialized exact algorithm, and the best-performing heuristics proposed for this problem. The proposed algorithms are competitive and offer strong results, mainly for large-scale auctions.

Avoiding Pitfalls Of Intraoperative Peripheral Endovascular Surgery With The Aid Of Osirix: Expanding The Use Of Virtual Fluoroscopy.

We have shown how the analysis of the angiotomography reconstruction through OsiriX program has assisted in endovascular perioperative programming. We presented its application in situations when an unexpected existence of metallic overlapping artifact (orthopedic osteosynthesis) compromised the adequate visualization of the arterial lesion during the procedure. Through manipulation upon OsiriX software, with assistance of preview under virtual fluoroscopy, it was possible to obtain the angles that would avoid this juxtaposition. These angles were reproduced in the C-arm, allowing visualization of the occluded segment, reducing the need for repeated image acquisitions and contrast overload, allowing the continuation of the procedure.