O ser humano tem uma grande estima pelo processo de raciocínio que desenvolveu durante a sua evolução. Uma das áreas da computação foi desenvolvida com o objetivo inicial de simular a inteligência humana dentro de programas computacionais. Esta área ficou conhecida como inteligência artificial. Nas últimas décadas a inteligência artificial tem se baseado nas mais diversas formas de organização que tenham padrões. Um desses métodos é o algoritmo de otimização por colônias de formigas, apresentado no início da década de 90, e que apresentou bons resultados para vários problemas que tiveram modelos implementados. A biologia molecular visa analisar as estruturas moleculares contidas nos seres vivos, dentre elas as seqüências de DNA, RNA e os aminoácidos das proteínas. Devido o grande número de informações envolvidas nessa análise torna-se inviável em termos de tempo de processamento uma busca em todo o espaço de soluções possíveis, o que torna interessante o uso de algoritmos que percorram este espaço de busca de forma eficiente. Um dos problemas da biologia molecular é a reconstrução de árvores filogenéticas. Ele visa relacionar de forma hereditária as diversas espécies através das informações contidas em suas seqüências. Desta forma é possível saber quais espécies são mais próximas em termos evolutivos. Outro problema é o dobramento de proteínas. Uma proteína é um polímero que pode desempenhar as mais diversas funções em um ser vivo. A função que uma proteína desempenha esta diretamente relaciona a sua forma tridimensional. Uma proteína é codificada no DNA, e sintetizada no ribossomo de uma forma linear, a partir desta forma ela se dobra sobre a sua estrutura obtendo a sua forma final. Com a compreensão deste processo, seria possível a identificação de proteínas mal formadas e até mesmo o desenvolvimento de novas proteínas com funções específicas. O presente trabalho visa descrever dos modelos, baseados na otimização por colônia de formigas, desenvolvidos para os problemas. Além disso, foram desenvolvidos recursos especiais que permitem percorrer o espaço de busca de forma mais efetiva obtendo melhores soluções. Os resultados obtidos com as metodologias propostas apresentaram resultados similares ou até melhores que métodos já conhecidos que utilizaram o algoritmo de otimização por colônia de formigas para os mesmos problemas. / The human being has great esteem for the reasoning process developed during its evolution. One of the areas of the computation was developed with the initial objective to simulate human intelligence inside computational programs. This area is known as artificial intelligence. In the last decades artificial intelligence has been basing on the most diverse forms of organization that have standards. One of these methods is the ant colony optimization algorithm, presented in the beginning of nineties, and that achieved good results for some problems that had had implemented models. Molecular biology aims to analyze the molecular structures present in living creatures, amongst them the sequences of DNA, RNA and protein aminoacids. Due to great number of information being confronted in this analysis it is impracticable in terms of processing time a search in the whole space of possible solutions, what makes interesting the use of algorithms that cover the search space efficiently. One of the problems of molecular biology is phylogenetic trees reconstruction. It aims to relate hereditarily the several species through information present in its sequences. In that manner, it is possible to know which species are more closely related to one another and which are more distantly related.

Este trabalho trata de uma aplicação de programação estocástica para administração de passivos e ativos. Inicialmente, um modelo de administração de ativos e passivos utilizando valores de retorno de ativos determinísticos é formalizado, constatando-se as suas limitações, justificando-se a necessidade de abranger formalmente a incerteza inerente aos mercados financeiros. Para isso, um modelo para administração de ativos e passivos que utiliza otimização e programação estocástica baseado em uma árvore de cenários multiestágio balanceada é apresentado, descrito, e implementado. Os seus resultados determinam uma política de investimento de ativos para o instante inicial do período considerado, definindo-se também uma regra que possibilita, a partir do equilíbrio entre o patrimônio inicial e total de passivo a ser pago ao final do período considerado, estimar a probabilidade de insolvência do fundo de pensão. Além disso, realiza-se o estudo do impacto da redução de uma proxy da taxa de juros básico na composição do portfólio administrado por essas empresas. / This work discusses an application of stochastic programming for asset-liability management. Initially, a deterministic asset-liability model is formalized. Its limitations become clear which justify the need to include uncertainty in the model. Then, a stochastic programming model based on a balanced multistage scenario tree is presented, described and implemented for an asset-liability environment. The main results are: (i) an investment policy for the fund, and, (ii) the pension’s fund insolvency probability considering an initial relation between the current assets and the present value of the future liabilities. The impact of a possible reduction in interested rate on the pension’s fund optimal portfolio is also presented.

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. / Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.

Este trabalho trata de uma aplicação de programação estocástica para administração de passivos e ativos. Inicialmente, um modelo de administração de ativos e passivos utilizando valores de retorno de ativos determinísticos é formalizado, constatando-se as suas limitações, justificando-se a necessidade de abranger formalmente a incerteza inerente aos mercados financeiros. Para isso, um modelo para administração de ativos e passivos que utiliza otimização e programação estocástica baseado em uma árvore de cenários multiestágio balanceada é apresentado, descrito, e implementado. Os seus resultados determinam uma política de investimento de ativos para o instante inicial do período considerado, definindo-se também uma regra que possibilita, a partir do equilíbrio entre o patrimônio inicial e total de passivo a ser pago ao final do período considerado, estimar a probabilidade de insolvência do fundo de pensão. Além disso, realiza-se o estudo do impacto da redução de uma proxy da taxa de juros básico na composição do portfólio administrado por essas empresas. / This work discusses an application of stochastic programming for asset-liability management. Initially, a deterministic asset-liability model is formalized. Its limitations become clear which justify the need to include uncertainty in the model. Then, a stochastic programming model based on a balanced multistage scenario tree is presented, described and implemented for an asset-liability environment. The main results are: (i) an investment policy for the fund, and, (ii) the pension’s fund insolvency probability considering an initial relation between the current assets and the present value of the future liabilities. The impact of a possible reduction in interested rate on the pension’s fund optimal portfolio is also presented.

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-13T19:39:00Z (GMT). No. of bitstreams: 1 Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5) Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:51:37Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_M.pdf: 1632808 bytes, checksum: dfd28dc2bbd2bb5fe453a2fb1c2b7b6e (MD5) Previous issue date: 2009 / Resumo: O objetivo desta dissertação é desenvolver uma metodologia eficiente para solucionar o problema de agrupamento capacitado multicritério (PACM), no qual objetos com pesos associados são dados, os quais devem ser particionados em agrupamentos com capacidade limitada. Neste trabalho, o PACM está ambientado em um problema de reagrupamento de lotes urbanos, nos quais devem ser realizadas as leituras dos medidores de energia elétrica por concessionárias de distribuição de energia. A operação de leitura dos medidores é realizada sobre lotes geograficamente definidos e é desempenhada sobre rotas percorridas uma vez por mês pelos leituristas. A motivação deste trabalho é atribuída ao fato de que, com o passar do tempo, o tamanho e o formato dos lotes vão ficando obsoletos, devido a modificações introduzidas na conformação atual, desarranjando o equilíbrio entre os lotes e desatualizando as rotas. Por esse motivo é importante realizar um reagrupamento dos lotes buscando a diminuição dos custos operacionais de leitura, assim como a minimização dos custos e transtornos causados pelas modificações. O método proposto para resolver o problema abordado nesta dissertação é um algoritmo baseado na metaheurística GRASP (Greedy randomized adaptive search procedure). A eficiência do método proposto é testada sobre uma série de instâncias geradas e sobre uma rede real. Os experimentos computacionais demonstram a eficiência do método. / Abstract: The aim of this dissertation is to develop an eficient methodology to solve the multicriteria redistricting capacitated problem (PACM), in which objects with associated weights are given, which must be partitioned into groups with limited capacity. In this work, the PACM is inserted in to a reassignment problem of urban clusters of clients, in which the readings of the eletric energy measurement must be performed by the company of energy distribution. The reading operation is performed over lots geographically defined is performed once a month by the readers. The motivation of this work is due to the fact that the size and shape of the lots become obsolete after some time, due to modifications introduced in the current conformation, desarranging the balance between the lots and outdating the routes. For this reason it is important to achieve a reassignment of the lots trying to decrease the operational costs of reading, as well as minimizing the costs and inconvenience caused by the changes. The proposed method to solve the problem addressed in this dissertation is a algorithm based on GRASP (Greedy randomized adaptive search procedure) metaheuristic. The efectiveness of the proposed method is tested on a large number of generated instances and on a real network. Computational experiments demonstrate the efectiveness of the proposed approach. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T05:36:32Z (GMT). No. of bitstreams: 1 Cavalcante_VictorFernandes_D.pdf: 1501954 bytes, checksum: afd9c038eef0eb384065875b1df282ca (MD5) Previous issue date: 2008 / Resumo: Uma das principais motivações para o estudo de Otimização Discreta reside no elevado número de problemas do nosso cotidiano representáveis através de modelos de Otimização Inteira e Combinatória. Em particular, muitos destes problemas podem ser formulados com Programação Inteira 0-1, o que desperta especial interesse em técnicas capazes de resolver tais modelos. Dentre as inúmeras formas de solução atualmente disponíveis para problemas desta natureza, os algoritmos baseados na técnica de relaxação Lagrangiana surgem como uma alternativa que tem tido grande sucesso na prática. Além disso, avanços consideráveis ocorreram na área de Programação Inteira com o advento da Combinatória Poliédrica, intensificando o interesse pelos algoritmos de planos de corte. Neste contexto, esta tese tem como principal objetivo verificar as potencialidades do uso combinado de Combinatória Poliédrica e relaxação Lagrangiana na resolução de dois problemas de otimização combinatória. Mais especificamente, o presente trabalho esta focado no desenvolvimento dos chamados algoritmos relax-and-cut para o problema de particionamento de conjuntos e ao problema do separador de vértices de um grafo. Sendo assim, são propostos algoritmos que combinam relaxação Lagrangiana e planos de cortes faciais para os dois problemas sob consideração. Em ambos os casos, os resultados obtidos com os testes computacionais realizados são comparados com os melhores resultados disponíveis na literatura. Os principais resultados alcançados na tese mostram que: (a) o uso combinado de relaxação Lagrangiana e planos de corte constitui uma alternativa bastante competitiva para solucionar o problema de particionamento de conjuntos, freqüentemente superando o desempenho dos melhores algoritmos disponíveis na literatura para o problema e, (b) no caso do problema do separador de vértices, além da combinação de técnicas Lagrangianas com o uso de planos de corte, a hibridização dos algoritmos relax-and-cut e branch-andcut leva á resolução de instâncias da literatura mais rapidamente que o melhor algoritmo exato conhecido para o problema até então. / Abstract: One of the main motivations for the study of Discrete Optimization resides in the huge number of problems from our daily life that can be represented through Integer and Combinatorial Optimization models. In particular, many of these problems can be cast as 0-1 Integer Programs, which gives rise to special interest on how to solve such models. Among the several ways currently available to solve problems of this nature, the algorithms based on Lagrangian relaxation techniques appears as an alternative that has had great success in practice. Besides, noticeable achievements occurred with the advent of Polyhedral Combinatorics, intensifying the interest on cutting plane algorithms. In this context, this thesis has as its main goal to verify the potentialities of the combined usage of Polyhedral Combinatorics and Lagrangian relaxation in the resolution of two combinatorial optimization problems. More specifically, the present work is focused on the development of the so-called relax-and-cut algorithms for the set partition problem and for the vertex separator problem on graphs. Therefore, algorithms combining Lagrangian relaxation and cutting planes are proposed for the two problems under consideration. In both cases, the results obtained in the computational tests carried out are compared with the best ones available in the literature. The main results achieved in the thesis show that: (a) the combined usage of Lagrangian relaxation and cutting planes constitutes a competitive alternative to solve the set partition problem, often outperforming the best algorithms available in the literature for the problem and, (b) in the case of the vertex separator problem, besides the combination of Lagrangian techniques and cutting planes, a hybridization of the relax-and-cut and branch-and-cut algorithms lead to the resolution of instances from the literature more rapidly than the best exact algorithm known for the problem so far. / Doutorado / Doutor em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T14:30:07Z (GMT). No. of bitstreams: 1 Mortati_CamilaFrederico_M.pdf: 341927 bytes, checksum: 5b1a9d9a8e6c0852c0e86425852e2584 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui proposto / Abstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work / Mestrado / Automação / Mestre em Engenharia Elétrica

Submitted by Pedro Henrique Rodrigues (pedro.henriquer@ufpe.br) on 2015-03-04T17:17:29Z No. of bitstreams: 2 dissert-avap.pdf: 401311 bytes, checksum: 5bd3f82323bd612e8265a6ab8a55eda0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-04T17:17:29Z (GMT). No. of bitstreams: 2 dissert-avap.pdf: 401311 bytes, checksum: 5bd3f82323bd612e8265a6ab8a55eda0 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2012-03-08 / Cloud reliance is critical to its success. Although fault-tolerance mechanisms are employed by cloud providers, there is always the possibility of failure of infrastructure components. We consequently need to think proactively of how to deal with the occurrence of failures, in an attempt to minimize their effects. In this work, we draw the risk concept from probabilistic risk analysis in order to achieve this. In probabilistic risk analysis, consequence costs are associated to failure events of the target system, and failure probabilities are associated to infrastructural components. The risk is the expected consequence of the whole system. We use the risk concept in order to present representative mathematical models for which computational optimization problems are formulated and solved, in a Cloud Computing environment. In these problems, consequence costs are associated to incoming applications that must be allocated in the Cloud and the risk is either seen as an objective function that must be minimized or as a constraint that should be limited. The proposed problems are solved either by optimal algorithm reductions or by approximation algorithms with provably performance guarantees. Finally, the models and problems are discussed from a more practical point of view, with examples of how to assess risk using these solutions. Also, the solutions are evaluated and results on their performance are established, showing that they can be used in the effective planning of the Cloud.