Problemas de programação matemática com restrições lineares de equilíbrio

Neste trabalho é desenvolvido um algoritmo enumerativo paramétrico de optimização global para a resolução de Problemas de Programação Matemática com Restrições de Equilíbrio ou de Complementaridade (MPEC). A comparação com outras técnicas globais da literatura é efectuada para um leque variado de problemas, de modo a poder avaliar a eficiência do processo proposto. A utilização de algoritmos de MPEC para a resolução de alguns problemas de optimização global é o outro grande objectivo desta tese. Nesse sentido são introduzidas novas formula¸c˜oes de programas bilineares e lineares complementares como MPECs. São ainda analisadas e discutidas formulaçõess MPEC para o problema de programação linear inteira 0-1, para a determinação do Conjunto Independente Máximo de um Grafo (MIS) e para a estimação do Número de Condição de uma Matriz. Para o problema MIS é desenvolvido um algoritmo de ramificação e limitação, baseado na decomposição de uma função quadrática numa diferença de duas funçõess convexas (DC). Finalmente é introduzida uma técnica MPEC local para a estimação do número de condição com a norma l1 e é estabelecido para matrizes de Minkowski que o número de condição nessa norma pode ser estimado com apenas um sistema de equações lineares. Em todos os desenvolvimentos houve uma grande preocupação em testar as novas formulações e algoritmos com problemas conhecidos da literatura, de modo a aferir da qualidade e interesse dessas propostas.

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.

Aceleração GPU da animação de superfícies deformáveis

Dissertação de Mestrado em Engenharia Informática

A contribuição da informática para o desenvolvimento sustentável: o exemplo do conceito de grid computing

Este trabalho foi realizado sob orientação do Prof. António Brandão Moniz para a disciplina “Factores Sociais da Inovação” do Mestrado Engenharia Informática realizado na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa (Portugal)

Mecanismos de suporte à execução concorrente de programas em lógica

Dissertacção apresentada para a obtenção do Grau de Mestre em Engenharia Informática pela Universidade Nova de Lisboa, Faculdade de Ciências e Tecnologia.

Modelação e integração em sistemas flexíveis de produção

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

Escalonamento de geradores térmicos com integração de produção eólica: uma abordagem baseada em programação inteira mista

A alta e crescente participação da energia eólica na matriz da produção traz grandes desafios aos operadores do sistema na gestão da rede e planeamento da produção. A incerteza associada à produção eólica condiciona os processos de escalonamento e despacho económico dos geradores térmicos, uma vez que a produção eólica efetiva pode ser muito diferente da produção prevista. O presente trabalho propõe duas metodologias de otimização do escalonamento de geradores térmicos baseadas em Programação Inteira Mista. Pretende-se encontrar soluções de escalonamento que minimizem as influências negativas da integração de energia eólica no sistema elétrico. Inicialmente o problema de escalonamento de geradores é formulado sem considerar a integração da energia eólica. Posteriormente foi considerada a penetração da energia eólica no sistema elétrico. No primeiro modelo proposto, o problema é formulado como um problema de otimização estocástico. Nesta formulação todos os cenários de produção eólica são levados em consideração no processo de otimização. No segundo modelo, o problema é formulado como um problema de otimização determinística. Nesta formulação, o escalonamento é feito para cada cenário de produção eólica e no fim determina-se a melhor solução por meio de indicadores de avaliação. Foram feitas simulações para diferentes níveis de reserva girante e os resultados obtidos mostraram que a alta participação da energia eólica na matriz da produção põe em causa a segurança e garantia de produção devido às características volátil e intermitente da produção eólica e para manter os mesmos níveis de segurança é preciso dispor no sistema de capacidade reserva girante suficiente capaz de compensar os erros de previsão.

Uma metaheurística para a programação de projectos com multi-modos e recursos limitados

Este artigo apresenta uma nova abordagem (MM-GAV-FBI), aplicável ao problema da programação de projectos com restrições de recursos e vários modos de execução por actividade, problema conhecido na literatura anglo-saxónica por MRCPSP. Cada projecto tem um conjunto de actividades com precedências tecnológicas definidas e um conjunto de recursos limitados, sendo que cada actividade pode ter mais do que um modo de realização. A programação dos projectos é realizada com recurso a um esquema de geração de planos (do inglês Schedule Generation Scheme - SGS) integrado com uma metaheurística. A metaheurística é baseada no paradigma dos algoritmos genéticos. As prioridades das actividades são obtidas a partir de um algoritmo genético. A representação cromossómica utilizada baseia-se em chaves aleatórias. O SGS gera planos não-atrasados. Após a obtenção de uma solução é aplicada uma melhoria local. O objectivo da abordagem é encontrar o melhor plano (planning), ou seja, o plano que tenha a menor duração temporal possível, satisfazendo as precedências das actividades e as restrições de recursos. A abordagem proposta é testada num conjunto de problemas retirados da literatura da especialidade e os resultados computacionais são comparados com outras abordagens. Os resultados computacionais validam o bom desempenho da abordagem, não apenas em termos de qualidade da solução, mas também em termos de tempo útil.

Análise de imagens tomográficas: visualização e paralelização de processamento

Dissertação de Mestrado em Engenharia Informática

Sistema de ficheiros transaccional sobre FUSE

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

tlCell: a software transactional memory for the cell broadband engine architecture

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

Contributos didático-pedagógicos do software smartmusic no ensino do clarinete

Mestrado em Ensino da Música.

Redes, comunicações e segurança informática

Este trabalho começa por apresentar uma instalação de rede informática local efetuada sob supervisão do candidato e parcialmente por ele, descrevendo de seguida algumas considerações que na altura se lhe levantaram. Sendo ligada à saúde, para além das preocupações normais de instalação de qualquer solução, a questão humana e social foi particularmente sentida. Várias organizações e pessoas individuais necessitam de implementar e utilizar soluções de comunicações informáticas, pelo que a privacidade e confiabilidade das informações processadas se torna um assunto premente. No sentido de obter uma resposta para este problema, o candidato evoluiu para a área da criptografia e segurança de comunicações, implementado alguns dos protocolos existentes e estudando-os com maior rigor. É justamente a descrição dessa evolução e da segurança com que se pode contar quando se utilizam meios informáticos o âmbito deste trabalho, focando principalmente o impacto que tem na sua utilização.

Aplicação informática para dimensionamento de barramentos em subestações

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações