A public transport bus assignment problem: parallel metaheuristics assessment

Combinatorial Optimization Problems occur in a wide variety of contexts and generally are NP-hard problems. At a corporate level solving this problems is of great importance since they contribute to the optimization of operational costs. In this thesis we propose to solve the Public Transport Bus Assignment problem considering an heterogeneous fleet and line exchanges, a variant of the Multi-Depot Vehicle Scheduling Problem in which additional constraints are enforced to model a real life scenario. The number of constraints involved and the large number of variables makes impracticable solving to optimality using complete search techniques. Therefore, we explore metaheuristics, that sacrifice optimality to produce solutions in feasible time. More concretely, we focus on the development of algorithms based on a sophisticated metaheuristic, Ant-Colony Optimization (ACO), which is based on a stochastic learning mechanism. For complex problems with a considerable number of constraints, sophisticated metaheuristics may fail to produce quality solutions in a reasonable amount of time. Thus, we developed parallel shared-memory (SM) synchronous ACO algorithms, however, synchronism originates the straggler problem. Therefore, we proposed three SM asynchronous algorithms that break the original algorithm semantics and differ on the degree of concurrency allowed while manipulating the learned information. Our results show that our sequential ACO algorithms produced better solutions than a Restarts metaheuristic, the ACO algorithms were able to learn and better solutions were achieved by increasing the amount of cooperation (number of search agents). Regarding parallel algorithms, our asynchronous ACO algorithms outperformed synchronous ones in terms of speedup and solution quality, achieving speedups of 17.6x. The cooperation scheme imposed by asynchronism also achieved a better learning rate than the original one.

Motivation drivers of millenniums for engaging in crowdsourcing ventures

Double Degree

Concurrent tabling

In the past few years Tabling has emerged as a powerful logic programming model. The integration of concurrent features into the implementation of Tabling systems is demanded by need to use recently developed tabling applications within distributed systems, where a process has to respond concurrently to several requests. The support for sharing of tables among the concurrent threads of a Tabling process is a desirable feature, to allow one of Tabling’s virtues, the re-use of computations by other threads and to allow efficient usage of available memory. However, the incremental completion of tables which are evaluated concurrently is not a trivial problem. In this dissertation we describe the integration of concurrency mechanisms, by the way of multi-threading, in a state of the art Tabling and Prolog system, XSB. We begin by reviewing the main concepts for a formal description of tabled computations, called SLG resolution and for the implementation of Tabling under the SLG-WAM, the abstract machine supported by XSB. We describe the different scheduling strategies provided by XSB and introduce some new properties of local scheduling, a scheduling strategy for SLG resolution. We proceed to describe our implementation work by describing the process of integrating multi-threading in a Prolog system supporting Tabling, without addressing the problem of shared tables. We describe the trade-offs and implementation decisions involved. We then describe an optimistic algorithm for the concurrent sharing of completed tables, Shared Completed Tables, which allows the sharing of tables without incurring in deadlocks, under local scheduling. This method relies on the execution properties of local scheduling and includes full support for negation. We provide a theoretical framework and discuss the implementation’s correctness and complexity. After that, we describe amethod for the sharing of tables among threads that allows parallelism in the computation of inter-dependent subgoals, which we name Concurrent Completion. We informally argue for the correctness of Concurrent Completion. We give detailed performance measurements of the multi-threaded XSB systems over a variety of machines and operating systems, for both the Shared Completed Tables and the Concurrent Completion implementations. We focus our measurements inthe overhead over the sequential engine and the scalability of the system. We finish with a comparison of XSB with other multi-threaded Prolog systems and we compare our approach to concurrent tabling with parallel and distributed methods for the evaluation of tabling. Finally, we identify future research directions.

Integrando problem frames com aspectos

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

A new approach to the initial value problem

5th Portuguese Conference on Automatic Control, September, 5-7, 2002, Aveiro, Portugal

Integrated ecological-economic modelling and assessment aproach for coastal ecosystem management

Thesis submitted to the Faculty of Sciences and Technology, New University of Lisbon, for the degree of Doctor of Philosophy in Environmental Sciences

A framework for scientific computing with GPUs

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Modeling assembly program with constraints. A contribution to WCET problem

Dissertação para obtenção do Grau de Mestre em Lógica Computacional

GIS capacity building for risk management to help developing countries:Case of climate change problem in Amhara rural region (Ethiopia)

Dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Geospatial Technologies.

Innovation at Polisport: Discoverding the drivers and impact on performance at a Portuguese SME

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Drivers of China's foreign direct investment into Africa

We assess the determinants of Chinese direct investment in Africa compared with those of global FDI. We find that economic size and macroeconomic stability are positively correlated with Chinese and global FDI in Africa. Institutional variables, such as accountability and rule of law, are not significant in either case and the same can be said about FDI-aid complementarities. The presence of oil is a determinant of Chinese FDI but not of global FDI into Africa. Conversely, the openness of the economy is a determinant for global FDI but not of Chinese FDI, which appears to favour closed economies possibly due to industrial organizational concerns. While these differences accord with intuition, we find no evidence for the claim that Chinese FDI in Africa is related to non-economic governance in a specific way that differs from global practice. More refined governance indicators should be used to verify whether Chinese and global FDI into Africa remain indistinguishable on this score: we plan to do this in future research.

The strategic drivers of the 'revolution': Harley-Davidson and Porsche

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Business model analysis of Mobitto: How to solve the chicken and egg problem of a multi-sided platform?

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Drivers and barriers to value creation in mobile service delivery

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Drivers of participation in collaborative consumption ventures

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics