[pt] A maioria das linguagens de programação modernas fornece ferramentas para programação concorrente sem restringir seu uso. Assim, fica a cargo do programador evitar a ocorrência de condições de corrida. Nessa dissertação, revisitamos o modelo de monitores, projetados para prevenir condições de corrida ao limitar o acesso à variáveis compartilhadas, e mostramos que monitores podem ser implementados em linguagens de programação com semântica referencial, dadas as regras de tipagem apropriadas. Nós descrevemos a linguagem de programação Aria, projetada com monitores nativos seguindo a proposta original do modelo. Através da resolução de problemas clássicos de concorrência, nós avaliamos o uso de monitores em Aria para sincronização em diferentes níveis de granularidade, e extendemos a linguagem com novos recursos a fim de contemplar as limitações do modelo envolvendo desempenho e expressividade. / [en] Most current programming languages do not restrict the use of the concurrency primitives they provide, leaving it to the programmer to detect data races. In this dissertation, we revisit the monitor model, which guards against data races by guaranteeing that accesses to shared variables occur only inside monitors, and show that this concept can be implemented in a programming language with referential semantics, given appropriate typing rules. We describe the Aria programming language, designed with native monitors according to these rules. Through the discussion of classic concurrency problems, we evaluate the use of Aria monitors for synchronization at different levels of granularity and extend the language with new features to address the limitations of monitors regarding performance and expressiveness.

[pt] Os problemas de alocação de recurso procuram encontrar uma repartição ideal de recursos a um número fixo de áreas. Nesta dissertação, consideramos um problema de alocação de recurso com uma função objetiva linear e dois conjuntos distintos de restrições: um conjunto de restrições aninhados, onde as somas parciais das variáveis de decisão são limitadas por cima e uma restrição linear que define um hiperplano. Propomos um algoritmo fracamente e um fortemente polinomial. O algoritmo fracamente polinomial requer algumas suposições sobre os dados e possui complexidade de O(n log n log |Λ|/|I|), onde n é o número de variáveis, Λ é um intervalo no espaço dual, e |I| está relacionado com a precisão dos dados. O algoritmo fortemente polinomial é baseado na técnica de busca paramétrica de Megiddo e obtém uma complexidade O(n log n). As complexidades obtidas são superiores à complexidade do método genérico de Pontos Interiores, O(n 3/ log n). Além disso, uma análise experimental foi realizada e os algoritmos mostraram-se mais eficientes e produziram soluções ótimas para instâncias de problemas com até 1.000.000 variáveis. / [en] The Resource Allocation Problems seek to find an optimal repartition of resources into a fixed number of areas. In this thesis, we consider a resource allocation problem with a linear objective and two distinct sets of constraints: a set of nested constraints, where the partial sums of the decision variables are limited from above and a linear constraint that defines a hyperplane. We propose a weakly and a strongly polynomial algorithm. The weakly polynomial algorithm requires certain assumptions of the data and runs in O(n log n log |Λ|/|I|) time, where n is the number of decision variables, Λ is an interval in the dual space, and |I| relates to the precision of the data. The strongly polynomial algorithm is based on Megiddo s parametric search technique, and obtains a complexity of O(n log n). These are large improvements upon the O(n 3/ log n) complexity of the generic Interior Point Method. In addition, an experimental analysis was carried out and the algorithms showed to be more efficient and produced optimal solutions for problem instances with up to 1,000,000 variables.

[pt] Alunos aprendendo programação concorrente muitas vezes têm dificuldades de testar seus programas por conta do não-determinismo presente no escalonamento de threads. Em geral, é difícil testar cenários específicos e mais difícil ainda repetir um determinado cenário para testar mudanças do código. Nesta tese, apresentamos a EventManager: uma ferramenta que criamos para permitir que um usuário instrumente seu programa, marcando eventos no código e especificando sequências de eventos através de uma linguagem de domínio específico (DSL). Esta linguagem restringe o escalonamento das threads para que obedeça as sequências permitidas para estes eventos. Descrevemos a implementação da EventManager para aplicações baseadas em threads POSIX. Investigamos a aplicação da ferramenta em soluções de problemas clássicos de concorrência para averiguar a expressividade da linguagem que criamos. / [en] Students learning concurrent programming often struggle with tests due to the non-deterministic nature of thread scheduling. It is in general hard to test specific scenarios and harder yet to repeat a given scenario for further tests after changes to the code. In this thesis, we present EventManager: a tool we developed that allows the user to instrument their program, marking events in the code and specifying valid event sequences using a domainspecific language. This language restricts thread scheduling to obey allowed sequences for these events. We describe the implementation of EventManager for applications based on POSIX threads. We investigate our tool applied on solutions of classical concurrency problems to verify the expressiveness of the created language.

[pt] O presente trabalho tem como foco o estudo do Sistema Petrobras, no que tange o planejamento estratégico dos investimentos da Companhia, sob a ótica da cadeia integrada do petróleo. A partir de um dos modelos matemáticos mais utilizados (e há mais tempo) na empresa, diversas decisões estratégicas de suma importância são suportadas, de modo a maximizar seu resultado operacional ao longo de um horizonte de tempo da ordem de 10 (dez) anos. Com embasamento na literatura atual, evoluções são propostas e testadas no modelo matemático. Primeiramente são introduzidas técnicas de programação estocástica em dois estágios, onde as decisões de investimento são representadas por variáveis de primeiro estágio; e a operação de todo o sistema – desde o refino até a comercialização do petróleo e derivados, passando por toda a questão logística – passa a fazer parte do segundo estágio, após a realização / revelação dos parâmetros estocásticos. Em um segundo passo, técnicas de decomposição são aplicadas para contornar eventuais limitações geradas pelo grande porte atingido pelo modelo, que cresce proporcionalmente ao número de cenários envolvidos na otimização. Os resultados mostram que o modelo estocástico começa a esbarrar nestas limitações a partir da resolução de problemas com mais de 30 cenários. Por outro lado, apesar do tempo computacional consideravelmente maior, o modelo decomposto chegou a resolver até 80 cenários, nos testes realizados. / [en] This work focuses on the study of Petrobras, regarding the strategic planning of the Company s investments, from an integrated oil supply chain perspective. From one of the most widely used mathematical models in the Company, several strategic decisions of great importance are supported, so as to maximize its operating result over a time horizon of approximately 10 (ten) years. Based in current literature, developments are proposed and tested in the mathematical model. First, two-stage stochastic programming techniques are introduced, where investment decisions are represented by first-stage variables; and system s operation – from oil refining and sales to the entire logistics issue – by second-stage variables, after realization of the stochastic parameters. In a second step, decomposition techniques are applied to circumvent any large scale limitations. The results show that the stochastic model starts to reach these limitations in problems with 30 scenarios or more. On the other hand, despite the considerably greater computational time, the decomposed model was able to solve up to 80-scenarios problems, during the tests.

[pt] Portfólios de fontes renováveis de energia elétrica são mecanismos de gerenciamento de risco interessantes para comercialização de energia em mercados de negociação bilateral. Quando formados por agentes que pertencem a diferentes companhias sua estabilidade depende da maneira com que os benefícios de mitigação de risco gerados pelo portfólio são alocados individualmente entre os participantes. O problema de se encontrar uma solução estável pode ser matematicamente formulado através da busca de um vetor de alocação de quotas que pertença ao núcleo do jogo cooperativo, que por sua vez pode ser formulado como um conjunto de restrições lineares que aumenta exponencialmente com o número de participantes. Adicionalmente, o lado direito de cada restrição que define o núcleo do jogo cooperativo define o valor de uma determinada coalisão que, no presente trabalho, é obtido através de um modelo de otimização estocástica de dois estágios. Este trabalho compara diferentes metodologias computacionalmente eficientes baseadas em programação linear inteira mista e na técnica de decomposição de Benders para encontrar vetores de alocação de quotas que pertençam ao núcleo de portfólios de larga escala de geradores de energia renovável. São apresentados estudos de casos que utilizam dados reais do sistema elétrico brasileiro. / [en] Portfolios of renewable electricity sources are interesting risk-management mechanisms for trading in electricity contract markets. When they are formed by players belonging to different companies, their stability relies on the way the riskmitigation benefit generated by the optimal portfolio is allocated through individual participants. The problem of reaching a stable allocation can be mathematically formulated in terms of finding a quota-sharing vector belonging to the Core of a cooperative game, which can be formulated as a set of linear constraints that exponentially grows with the number of participants. Moreover, the right-hand-side of each constraint defining the Core relies on a given coalition value which, in the present work, is obtained by a two-stage stochastic optimization model. This work presents and compares efficient methodologies mainly based on mixed integer linear programming and Benders decomposition to find quota allocation vectors that belongs to the Core of large-scale renewable energy portfolios. Case studies are presented with realistic data from the Brazilian power system.

[pt] Esta dissertação investiga o uso da Programação Genética para otimização estrutural de aglomerados de carbono. O objetivo primordial do estudo de cálculos que descrevam as interações de um aglomerado é encontrar o arranjo de átomos que corresponde à menor energia, ou àqueles que possuem energias próximas, já que estes são os candidatos mais prováveis de serem formados. Recentemente, na área da Inteligência Computacional, estudos apresentaram um novo método de otimização, chamado de Otimização por Programação Genética (OPG), com resultados promissores, avaliados em diversos casos de referência. A partir destes resultados, esta pesquisa aplica, de forma inédita, a abordagem OPG em problemas de otimização estrutural de aglomerados. Para fins de comparação, foram realizadas otimizações independentes utilizando o modelo tradicional de Algoritmos Genéticos (AGs). Neste trabalho, foram realizados vários ensaios computacionais utilizando os métodos OPG e AG para otimizar a geometria, ou seja, encontrar a estrutura de menor energia, de aglomerados de carbono de 5 a 25 átomos. Para o cálculo da energia, foi utilizado o potencial de Morse. Os valores das energias encontrados e as geometrias de cada aglomerado foram comparados com casos já publicados na literatura. Os resultados mostraram que, para os aglomerados menores, os dois métodos foram capazes de encontrar os mínimos globais, mas com o aumento do número de átomos, o OPG apresenta resultados superiores ao AG. Quanto ao tempo de execução por avaliação, o AG se mostrou significativamente mais rápido do que o do OPG, devido à sua representação direta das posições dos átomos, de um aglomerado, em um cromossomo. Porém a superioridade dos resultados OPG em relação ao AG indicou que a melhoria na sua implementação poderá ser de grande utilidade na área de simulação de aglomerados atômicos ou moleculares. / [en] This dissertation investigates the use of Genetic Programming for the structural optimization of carbon clusters. The main objective concerning computations that describe the interactions of a cluster is to find the arrangements of atoms corresponding to the lowest energy, since these are the most likely candidates to be formed. It has been recently introduced in the area of Computational Intelligence a new optimization method, called Optimization by Genetic Programming (OGP), showing promising results for several benchmark cases. Based on these results, the present work aimed at the application of OGP for the geometry optimization of carbon clusters. For comparison purposes, independent optimizations using the standard genetic algorithm (GA) approach were carried out. Several optimization trials were performed using both GA and OGP in order to find the best geometries of carbon clusters with size ranging from 5 to 25 atoms. The energy was calculated using the Morse potential. Resulting energies and geometries were compared to previously published results. Both GA and OGP were able to find the global minimum for the smaller clusters. However, upon increasing the number of atoms, the OGP presented better results compared to the GA. Concerning the execution time for each evaluation, the GA is significantly faster than the OGP due to its direct representation of the positions of atoms of a cluster in a chromosome. However, the superiority of the OGP results compared to the GA results suggests that an effort towards the improvement of the implementation of OGP could lead to a very powerful optimization tool to be used by the scientific community.

[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados. Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.

[pt] Os Problemas de Roteamento de Veículos estão entre os problemas combinatoriais mais difíceis de se resolver à otimalidade. Eles foram propostos no final da década de 1950, e desde então eles têm sido amplamente estudados. O interesse deve-se a sua importância prática, bem como da dificuldade de se fornecer algoritmos eficientes para resolvê-los. Esta tese trata principalmente da resolução exata do Problema de Roteamento de Veículos com Capacidades (PRVC). Neste problema, um conjunto de clientes, cada um associado a uma demanda, deve ser atendido por uma frota de veículos. Todos eles têm o mesma capacidade e, inicialmente, estão localizados no mesmo depósito. Uma solução é um conjunto de rotas que começam e terminam no depósito e visitam cada cliente uma única vez. A restrição em uma rota é que a soma das demandas de seus clientes não exceda a capacidade do veículo. O objetivo é encontrar uma solução com um custo mínimo. Os melhores algoritmos exatos para o PRVC desenvolvidos nos últimos dez anos são baseados na combinação de geração de cortes e colunas. Alguns autores utilizaram apenas cortes sobre as variáveis da formulação original, com a finalidade de manter o subproblema de geração de colunas relativamente fácil. Outros puderam reduzir os limites duais utilizando também um número restrito de cortes expressos nas variáveis do problema mestre, parando de incluir tais cortes quando o subproblema tornavase proibitivamente difícil. Uma família eficaz de tais cortes são os Subset Row Cuts. Esta tese apresenta uma técnica para reduzir consideravelmente o impacto que tais cortes causam no subproblema de geração de colunas, permitindo assim que muito mais cortes sejam adicionados. O novo algoritmo Branch-Cut-and-Price proposto também incorpora e combina pela primeira vez vários elementos presentes em trabalhos anteriores, como enumeração de rotas, fixação de variáveis e strong branching. Todas as instâncias usadas em algoritmos exatos, com até 199 clientes, foram resolvidas à otimalidade. Além disso, algumas maiores, com até 360 clientes, apenas consideradas antes em métodos heurísticos, também foram resolvidas. / [en] Vehicle Routing Problems are among the most difficult combinatorial problems to solve to optimality. They were proposed in the late 1950 s and since then have been widely studied. This interest arises from their practical importance, as well as the difficulty of providing efficient algorithms to solve them. This thesis is mainly concerned with the exact resolution of the Capacitated Vehicle Routing Problem (CVRP). In this problem, a set of customers, each one associated to a demand, must be serviced by a fleet of vehicles. All vehicles have the same (limited) capacity and initially are located in the same central depot. A solution is a set of routes, starting and ending at the depot, that visit every customer exactly once. The only constraint on a route is that the sum of the demands of its customers does not exceed the vehicle capacity. The objective is to find a solution with minimum total cost. The best performing exact algorithms for the CVRP developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts. This thesis introduces a technique for greatly reducing this impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration, variable fixing and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.

[pt] Smartphones se tornaram uma parte integrante da vida de muitas pessoas. Podemos usar esses dispositivos para executar uma grande variedade de tarefas, que vão desde dar telefonemas a acessar a Internet. No entanto, às vezes gostaríamos que algumas tarefas fossem executadas automaticamente. Estas tarefas podem ser automatizadas usando aplicativos de automação, os quais monitoram continuamente o contexto do smartphone para realizar um conjunto de ações quando um evento acontece sob certas condições. Estas automações estão começando a ficar popular entre os usuários finais, uma vez que elas podem tornar os celulares mais fáceis de usar e ainda mais eficientes no uso da bateria. No entanto, pouco foi feito para capacitar os usuários finais a criar tais automações. Propomos uma abordagem para automatizar tarefas de smartphones por demonstração retrospectiva. Sucintamente, consideramos a lógica por trás da abordagem como sendo continue fazendo o que eu acabo de fazer : a aplicação de automação grava continuamente as interações dos usuários com seus telefones, e depois que os usuários realizaram uma tarefa que eles gostariam de automatizar, basta eles pedirem à aplicação para criar uma regra de automação com base em suas últimas ações gravadas. Como os usuários só têm que usar seus smartphones, como eles naturalmente fariam, para demonstrar automações, acreditamos que a nossa abordagem pode reduzir a dificuldade na criação de automações de smartphones. Para avaliar a nossa abordagem, desenvolvemos protótipos de um aplicativo chamado Keep Doing It, que permite automatizar tarefas por demonstração. Realizamos um estudo em laboratório com o primeiro protótipo para coletar as primeiras impressões dos participantes. Os participantes tiveram que criar regras de automação usando o nosso aplicativo com base em cenários pré-determinados. Baseado no feedback dos participantes e na nossa observação, nós refinamos o protótipo e realizamos um estudo remoto de cinco dias com novos participantes, os quais desta vez podiam criar quais e quantas regras quisessem. No geral, os resultados de ambos os estudos sugerem que, embora houvesse algumas ocasionais imprecisões (especialmente ao demonstrar regras que contêm condições), os participantes gostariam de automatizar tarefas de smartphones por demonstração devido à facilidade de uso. Concluiu-se que esta abordagem tem muito potencial para ajudar os usuários finais a automatizar seus smartphones, mas ainda há questões que precisam ser abordadas em pesquisas futuras. / [en] Smartphones have become an integral part of many people s lives. We can use these powerful devices to perform a great variety of tasks, ranging from making phone calls to connecting to the Internet. However, sometimes we would like some tasks to be performed automatically. These tasks can be automated by using automation applications, which continuously monitor the smartphone s context to execute a sequence of actions when an event happens under certain conditions. These automations are starting to get popular with end users, since they can make their phones easier to use and even more battery efficient. However, little work has been done on empowering end users to create such automations. We propose an approach for automating smartphone tasks by retrospective demonstration. Succinctly, we consider the logic behind the approach as keep doing what I just did: the automation application continuously records the users interactions with their phones, and after users perform a task that they would like to automate, they can ask the application to create an automation rule based on their latest recorded actions. Since users only have to use their smartphones, as they would naturally do, to demonstrate the actions, we believe that our approach can lower the barrier for creating smartphone automations. To evaluate our approach, we developed prototypes of an application called Keep Doing It, which supports automating tasks by demonstration. We conducted a lab user study with the first prototype to gather participants first impressions. The participants created automation rules using our application based on given scenarios. Based on their feedback and on our observations, we refined the prototype and conducted a five-day remote user study with new participants, who could then create which and how many rules they wanted. Overall, the findings of both studies suggest that, although there were some occasional inaccuracies (especially when demonstrating rules that contain conditions), participants would be willing to automate smartphone tasks by demonstration due to its ease of use. We concluded that this approach has much potential to aid end users to automate their smartphones, but there are still issues that need to be addressed by further research.

[pt] Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.