A Inteligência de Enxame (Swarm Intelligence) é uma área de estudos que busca soluções para problemas de otimização utilizando-se de técnicas computacionais inspiradas no comportamento social emergente encontrado na biologia. A metaheurística Particle Swarm Optimization (PSO) é relativamente nova e foi inspirada no comportamento social de bandos de pássaros. PSO tem apresentado bons resultados em alguns trabalhos recentes de otimização discreta, apesar de ter sido concebido originalmente para a otimização de problemas contínuos. Este trabalho trata o Problema de Atribuição de Tarefas - Task Assignment Problem (TAP), e apresenta uma aplicação: o problema de alocação de táxis e clientes, cujo objetivo da otimização está em minimizar a distância percorrida pela frota. Primeiramente, o problema é resolvido em um cenário estático, com duas versões do PSO discreto: a primeira abordagem é baseada em codificação binária e a segunda utiliza permutações para codificar as soluções. Os resultados obtidos mostram que a segunda abordagem é superior à primeira em termos de qualidade das soluções e tempo computacional, e é capaz de encontrar as soluções ótimas para o problema nas instâncias para as quais os valores ótimos são conhecidos. A partir disto, o algoritmo é adaptado para a otimização do problema em um ambiente dinâmico, com a aplicação de diferentes estratégias de resposta às mudanças. Os novos resultados mostram que a combinação de algumas abordagens habilita o algoritmo PSO a obter boas soluções ao longo da ocorrência de mudanças nas variáveis de decisão problema, em todas as instâncias testadas, com diferentes tamanhos e escalas de mudança. / Swarm Intelligence searches for solutions to optimization problems using computational techniques inspired in the emerging social behavior found in biology. The metaheuristic Particle Swarm Optimization (PSO) is relatively new and can be considered a metaphor of bird flocks. PSO has shown good results in some recent works of discrete optimization, despite it has been originally designed for continuous optimization problems. This paper deals with the Task Assignment Problem (TAP), and presents an application: the optimization problem of allocation of taxis and customers, whose goal is to minimize the distance traveled by the fleet. The problem is solved in a static scenario with two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach is superior than the first one in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values in the tested instances of the problem. From this, the algorithm is adapted for the optimization of the problem in a dynamic environment, with the application of different strategies to respond to changes. The new results show that some combination of approaches enables the PSO algorithm to achieve good solutions along the occurrence of changes in decision variables problem, in all instances tested, with different sizes and scales of change.

Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.

Esta tese apresenta um estudo sobre modelagem computacional onde são aplicadas meta-heurísticas de otimização na solução de problemas inversos de transferência radiativa em meios unidimensionais com albedo dependente da variável óptica, e meios unidimensionais de duas camadas onde o problema inverso é tratado como um problema de otimização. O trabalho aplica uma meta-heurística baseada em comportamentos da natureza conhecida como algoritmo dos vagalumes. Inicialmente, foram feitos estudos comparativos de desempenho com dois outros algoritmos estocásticos clássicos. Os resultados encontrados indicaram que a escolha do algoritmo dos vagalumes era apropriada. Em seguida, foram propostas outras estratégias que foram inseridas no algoritmo dos vagalumes canônico. Foi proposto um caso onde se testou e investigou todas as potenciais estratégias. As que apresentaram os melhores resultados foram, então, testadas em mais dois casos distintos. Todos os três casos testados foram em um ambiente de uma camada, com albedo de espalhamento dependente da posição espacial. As estratégias que apresentaram os resultados mais competitivos foram testadas em um meio de duas camadas. Para este novo cenário foram propostos cinco novos casos de testes. Os resultados obtidos, pelas novas variantes do algoritmo dos vagalumes, foram criticamente analisados. / This thesis presents a study on computational modeling where optimization metaheuristics are applied to the solution of inverse radiative transfer problems in heterogeneous media: in one-layer media with space-dependent single scattering albedo, and two-layer media, where the inverse problem is formulated as an optimization problem. It is applied a metaheuristic based on the natural behavior of fireflies, known as the firefly algorithm. Initially, comparative studies of performance were made with two other classic stochastic algorithms. The results indicated that the choice of the firefly algorithm was appropriate. Then, it was proposed other strategies that have been inserted into the original firefly algorithm. A first case was proposed where all the strategies were investigated and tested. The strategies with the best results were investigated in other two different cases. All the three proposed cases involved one-layer media with space-dependent scattering albedo. The strategies have been tested and evaluated, and those which presented the best competitive results were then implemented for radiative problems in two-layer media. For this new scenario five test cases were investigated, and the results obtained with the new strategies developed in this work were critically analyzed.

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual / Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Optimization problems are interesting both from the theoretical and practical point of view. In this thesis we address this subject, presenting problems of analytical nature, algebraic, geometric and combinatorial that can be addressed in basic education. Our main goal is to show how much content already taught in school can be used in attractive way for students through real-world problems can be solved with the use of mathematics. Also tried to suggest some topics that, although not part of the standard curriculum can be implemented by integrating diverse part. / Problemas de otimização são interessantes tanto do ponto de vista teórico quanto prático. Nesta dissertação abordamos este assunto, apresentando problemas de natureza analítica, algébrica, geométrica e combinatória que podem ser abordados no ensino básico. Nosso principal objetivo é evidenciar como muito dos conteúdos já ensinados na escola podem ser utilizados de forma atrativa para os alunos, através de problemas do cotidiano que podem ser resolvidos com o uso da matemática. Também experimentamos sugerir alguns temas que, embora não façam parte do currículo padrão, podem ser implementados integrando a parte diversificada.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

Entre os maiores desafios existentes para a cultura da soja, os estresses bióticos e abióticos se destacam e a incidência de patógenos como a ferrugem asiática, causam grandes perdas aos produtores. No Brasil, a ferrugem é a principal causa de prejuízos nas lavouras e estratégias para o seu controle mais eficiente são necessárias. O melhoramento genético para a tolerância constitui uma importante ferramenta para manter a ferrugem em níveis abaixo de dano econômico por um período mais duradouro. Outro aspecto importante da cultura da soja é relacionado com a sua utilização, destacando-se a produção de farelo com alto teor de proteína e de óleo comestível e combustível. Apesar de apresentar uma rica composição nutricional, o seu uso direto na alimentação humana ainda não é comum no Brasil. Uma das formas de incluir a soja na dieta é na forma de hortaliça, também conhecida como Edamame, em que as vagens são colhidas ainda verdes ou imaturas (estádio R6) e os grãos consumidos após breve cozimento. Contudo, poucos esforços têm sido dedicados para desenvolver novos genótipos com boa performance agronômica e adequados ao consumo humano. O presente trabalho teve o objetivo de avaliar genótipos de soja para a produção de soja hortaliça que apresentem tolerância à ferrugem. Para isto foram realizados cruzamentos entre seis genitores com boas características agronômicas em um esquema dialélico 6x6, gerando 15 cruzamentos. Estes genótipos foram avaliados nas gerações F2 e F3 para a produtividade e o tamanho das sementes, sendo que na geração F3, foram adicionados outros dez caracteres. Nas duas gerações, foi estimada a sua tolerância à ferrugem, utilizando manejos diferentes da doença com fungicidas. Foram realizadas análises de variância individuais e conjuntas, agrupamento de médias, análises dialélicas, tendo sido estimados os coeficientes de herdabilidade e correlações entre os caracteres. As análises mostraram a existência de variabilidade entre os genótipos avaliados e indicaram que os cruzamentos apresentaram desempenho superior aos genitores para caracteres importantes. O uso dos diferentes manejos da ferrugem com fungicidas mostrou-se eficiente uma vez que foi possível identificar genótipos tolerantes. Além disso, foram detectadas interações genótipos x ambientes significativas, fato que representou um desafio para a seleção dos melhores genótipos. Os genitores BRS 267, USP 13-66.136 e USP 13-19.007 destacaram-se por apresentar estimativas altas de capacidade de combinação e os cruzamentos USP 13-66.136 x USP 13-19.007, USP 13-66.136 x USP 13-19.034, BRS 267 x USP 13-19.007 e Tengamine x USP 13-19.007 apresentaram os melhores desempenhos. As estimativas de capacidade específica de combinação (Sii) dos genitores indicaram a existência de divergência entre eles e os caracteres apresentaram altas herdabilidades. A magnitude e a significância das correlações indicaram a possibilidade de seleção de genótipos precoces com sementes grandes e, também, evidenciaram que a seleção de genótipos com período mais longo entre R6 e R7 (SGR6) beneficia a produtividade. Portanto, foi possível identificar genitores e cruzamentos promissores para o desenvolvimento de novas linhagens apropriadas para a produção de soja hortaliça com tolerância à ferrugem. / Among the major challenges for soybean cultivation, biotic and abiotic stresses stand out and the incidence of pathogens such as Asian rust can cause extensive losses to farmers. In Brazil, rust is the main cause of crop damage and strategies for a more efficient control are necessary. Breeding for tolerance is an important tool to keep rust below economic damage for a longer period. Another important aspect of the soybean crop is related to its use, which is directed to the production of high-protein meal, edible oil and fuel. Although this legume has a rich nutritional composition, its direct use in the diet is still not common in Brazil. One of the ways to use soybean as food is in the form of vegetable, also known as Edamame, in which the pods are harvested green or immature (R6 stage) and the grains consumed after brief cooking. However, few efforts have been devoted to developing new soybean genotypes with good agronomic performance and characteristics suitable for human consumption. The present research had the objective of evaluating soybean genotypes for the production of vegetable soybean with rust tolerance. For this, crosses between six parents with good agronomic characteristics were performed in a 6x6 diallel scheme, generating 15 crosses. These genotypes were evaluated in the F2 and F3 generations for seed yield and size, and in the F3 generation, ten other traits were added. In both generations, tolerance to rust was estimated in experiments designed for different managements of the disease with fungicides. Individual and joint analyzes of variance, grouping of means, diallel analyzes, and estimation of heritability and correlation coefficients were performed. The analyzes showed the existence of variability among the evaluated genotypes and indicated that the crosses presented superior performance to the parents for important traits. The use of different rust managements with fungicides was efficient, since it was possible to identify tolerant genotypes. In addition, significant genotypes x environments interactions were detected, a fact that represented a challenge for the selection of the best genotypes. The parents BRS 267, USP 13-66136 and USP 13-19007 stood out for presenting high estimates of general combining ability and the crosses USP 13-66136 x USP 13-19007, USP 13-66136 x USP 13-19034, BRS 267 x USP 13-19007 and Tengamine x USP 13-19.007 presented the best performances. Estimates of specific combining ability (Sii) of the parents indicated divergence between them and the traits showed high estimates of heritability. The magnitude and significance of the correlations indicated the possibility of selecting early genotypes with large seeds and showed that the selection of genotypes with a longer period between R6 and R7 (SGR6) benefits seed yield. Therefore, it was possible to identify promising parents and crosses for the development of new lines suitable for the production of vegetable soybean with rust tolerance.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.