Constraint-based modeling of minimum set covering: application to species differentation

Work presented in the context of the European Master in Computational Logics, as partial requisit for the graduation as Master in Computational Logics

Efficient Legendre spectral tau algorithm for solving two-sided space-time Caputo fractional advection-dispersion equation

In this paper we present the operational matrices of the left Caputo fractional derivative, right Caputo fractional derivative and Riemann–Liouville fractional integral for shifted Legendre polynomials. We develop an accurate numerical algorithm to solve the two-sided space–time fractional advection–dispersion equation (FADE) based on a spectral shifted Legendre tau (SLT) method in combination with the derived shifted Legendre operational matrices. The fractional derivatives are described in the Caputo sense. We propose a spectral SLT method, both in temporal and spatial discretizations for the two-sided space–time FADE. This technique reduces the two-sided space–time FADE to a system of algebraic equations that simplifies the problem. Numerical results carried out to confirm the spectral accuracy and efficiency of the proposed algorithm. By selecting relatively few Legendre polynomial degrees, we are able to get very accurate approximations, demonstrating the utility of the new approach over other numerical methods.

An efficient numerical scheme for solving multi-dimensional fractional optimal control problems with a quadratic performance index

The shifted Legendre orthogonal polynomials are used for the numerical solution of a new formulation for the multi-dimensional fractional optimal control problem (M-DFOCP) with a quadratic performance index. The fractional derivatives are described in the Caputo sense. The Lagrange multiplier method for the constrained extremum and the operational matrix of fractional integrals are used together with the help of the properties of the shifted Legendre orthonormal polynomials. The method reduces the M-DFOCP to a simpler problem that consists of solving a system of algebraic equations. For confirming the efficiency and accuracy of the proposed scheme, some test problems are implemented with their approximate solutions.

Cutting path as a rural postman problem

The Rural Postman Problem (RPP) is a particular Arc Routing Problem (ARP) which consists of determining a minimum cost circuit on a graph so that a given subset of required edges is traversed. The RPP is an NP-hard problem with significant real-life applications. This paper introduces an original approach based on Memetic Algorithms - the MARP algorithm - to solve the RPP and, also deals with an interesting Industrial Application, which focuses on the path optimization for component cutting operations. Memetic Algorithms are a class of Metaheuristics which may be seen as a population strategy that involves cooperation and competition processes between population elements and integrates “social knowledge”, using a local search procedure. The MARP algorithm is tested with different groups of instances and the results are compared with those gathered from other publications. MARP is also used in the context of various real-life applications.

Modeling assembly program with constraints. A contribution to WCET problem

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

Heurísticas de pesquisa local para problemas de máquina única

O escalonamento é uma das decisões mais importantes no funcionamento de uma linha de produção. No âmbito desta dissertação foi realizada uma descrição do problema do escalonamento, identificando alguns métodos para a optimização dos problemas de escalonamento. Foi realizado um estudo ao caso do problema de máquina única através do teste de várias instâncias com o objectivo de minimizar o atraso pesado, aplicando uma Meta-Heurística baseada na Pesquisa Local e dois algoritmos baseados no SB. Os resultados obtidos reflectem que os algoritmos baseados no SB apresentaram resultados mais próximos do óptimo, em relação ao algoritmo baseado na PL. Os resultados obtidos permitem sustentar a hipótese de não existirem algoritmos específicos para os problemas de escalonamento. A melhor forma de encontrar uma solução de boa qualidade em tempo útil é experimentar diferentes algoritmos e comparar o desempenho das soluções obtidas.

Non emergency patients transport - a mixed integer linear programming

This work presents a model and a heuristic to solve the non-emergency patients transport (NEPT) service issues given the new rules recently established in Portugal. The model follows the same principle of the Team Orienteering Problem by selecting the patients to be included in the routes attending the maximum reduction in costs when compared with individual transportation. This model establishes the best sets of patients to be transported together. The model was implemented in AMPL and a compact formulation was solved using NEOS Server. A heuristic procedure based on iteratively solving problems with one vehicle was presented, and this heuristic provides good results in terms of accuracy and computation time.

Genetic algorithms for the non emergency patients transport service

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the paper. The authors would like to thank Dr. Elaine DeBock for reviewing the manuscript.

Algorithms and tools for in silico design of cell factories

PhD thesis in Bioengineering

Otimização com restrições de complementaridade: algoritmos e aplicações

Tese de Doutoramento em Engenharia Industrial e de Sistemas (PDEIS)

Solving large 0–1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm

The artificial fish swarm algorithm has recently been emerged in continuous global optimization. It uses points of a population in space to identify the position of fish in the school. Many real-world optimization problems are described by 0-1 multidimensional knapsack problems that are NP-hard. In the last decades several exact as well as heuristic methods have been proposed for solving these problems. In this paper, a new simpli ed binary version of the artificial fish swarm algorithm is presented, where a point/ fish is represented by a binary string of 0/1 bits. Trial points are created by using crossover and mutation in the different fi sh behavior that are randomly selected by using two user de ned probability values. In order to make the points feasible the presented algorithm uses a random heuristic drop item procedure followed by an add item procedure aiming to increase the profit throughout the adding of more items in the knapsack. A cyclic reinitialization of 50% of the population, and a simple local search that allows the progress of a small percentage of points towards optimality and after that refines the best point in the population greatly improve the quality of the solutions. The presented method is tested on a set of benchmark instances and a comparison with other methods available in literature is shown. The comparison shows that the proposed method can be an alternative method for solving these problems.

MOEA/VAN: Multiobjective Evolutionary Algorithm based on Vector Angle Neighborhood

Natural selection favors the survival and reproduction of organisms that are best adapted to their environment. Selection mechanism in evolutionary algorithms mimics this process, aiming to create environmental conditions in which artificial organisms could evolve solving the problem at hand. This paper proposes a new selection scheme for evolutionary multiobjective optimization. The similarity measure that defines the concept of the neighborhood is a key feature of the proposed selection. Contrary to commonly used approaches, usually defined on the basis of distances between either individuals or weight vectors, it is suggested to consider the similarity and neighborhood based on the angle between individuals in the objective space. The smaller the angle, the more similar individuals. This notion is exploited during the mating and environmental selections. The convergence is ensured by minimizing distances from individuals to a reference point, whereas the diversity is preserved by maximizing angles between neighboring individuals. Experimental results reveal a highly competitive performance and useful characteristics of the proposed selection. Its strong diversity preserving ability allows to produce a significantly better performance on some problems when compared with stat-of-the-art algorithms.

Sistema de visão robótico baseado no sensor kinect para orientação no espaço e contorno de obstáculos

Dissertação de mestrado em Engenharia Eletrónica Industrial e Computadores (área de especialização em Robótica)

Development of an intelligent earthwork optimization system

Tese de Doutoramento em Engenharia Civil.

Polynomial-time complexity for instances of the endomorphism problem in free groups

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism Φ of F sending W to U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two- generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.