Orientador: Marcia A. Gomes Ruggiero / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:37:23Z (GMT). No. of bitstreams: 1 Haeser_Gabriel_M.pdf: 906525 bytes, checksum: ea7e3eb42abe6b8b451f99c4c63a3da4 (MD5) Previous issue date: 1996 / Resumo: Neste trabalho estudamos a teoria de algumas heurísticas para otimização global, e também a generalização do algoritmo genético de Aarts, Eiben e van Hee. Propomos um algoritmo para otimização global de problemas canalizados e diferenciáveis utilizando simulated annealing e o solver local GENCAN. Experimentos numéricos com o problema OVO ( Order- Value Optimization) são apresentados, e também com 28 problemas clássicos da literatura. Para problemas de otimização com restrições, apontamos idéias de como utilizar solvers locais e heurísticas globais em busca de bons algoritmos para otimização global, e propomos um algoritmo baseado em simulated annealing com solver local ALGENCAN / Abstract: In this work we study the theory behind some classical heuristics for global optimization, and a generalization of genetic algorithms from Aarts, Eiben and van Hee. We propose an algorithm for global optimization of box-constrained differentiable problems, using simulated annealing and the local solver GENCAN. Numerical experiments are presented for the OVO problem (Order-Value Optimization) and 28 classical problems. For general nonlinear programming problems, we mention some ideas of how to use local solvers and global heuristics towards good algorithms for global optimization, we also propose an algorithm based on simulated annealing with local solver ALGENCAN / Mestrado / Otimização / Mestre em Matemática Aplicada

Orientador: Raul Vinhas Ribeiro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T02:43:23Z (GMT). No. of bitstreams: 1 AraujoNeto_FranciscoCiliaode_M.pdf: 1886300 bytes, checksum: 7f7be0f39b44f4f0126206eb89016e20 (MD5) Previous issue date: 2005 / Resumo: Com o amadurecimento da tecnologia de multiplexação por comprimentos de onda ¿ WDM (Wavelength Division Multiplexing) e a crescente popularização de aplicações multidifusão, como teleconferência, o suporte a esse tipo de transmissão na camada WDM é um tópico importante a ser estudado. Uma particularidade no roteamento de comunicações multidifusão, devido ao alto custo, é o limite no número de comutadores (switches) capazes de dividir o sinal de luz para mais de um destino. Esse limite introduz o problema de alocação desse tipo de comutador nos nós da rede de forma a facilitar o roteamento multidifusão. Além de considerações sobre o aspecto topológico da rede, outras particularidades do problema de roteamento e alocação de comprimentos de onda são as degenerações da camada física da rede óptica, que proporcionam algumas restrições de potência no sinal óptico. Esse trabalho apresenta uma heurística para solução de dois problemas. O problema de alocação de divisores do sinal de luz (splitters), de roteamento e de alocação de comprimento de onda para comunicações multidifusão e o problema de roteamento e alocação de comprimentos de onda considerando restrições de potência na camada física da rede óptica. Experimentos indicam que a heurística proposta apresenta um bom compromisso entre rapidez e qualidade de solução / Abstract: Due to the WDM (Wavelength Division Multiplexing) technology maturity and the growing popularization of multicast applications, such as teleconference, the support to this type of transmission in WDM layer must be exploited. An issue in routing multicast connections, due to the high cost, is the limited number of switches capable of divide the light signal to more than one destination. This limit introduces the allocation problem of these kind of switches in the nodes of network with objective of facilitate the multicast routing. Despite these topologic issues of the network, other particularities of the routing and wavelength assignment problem are the power issues in the physical layer, which take some power restrictions in optical signal. This work presents a heuristic to solve two problems. The problem of Splitter placement, multicast routing and wavelength assignment and the problem of routing and wavelength assignment with power issues in physical layer in optical network. Experiments indicate that the heuristic presents a good tradeoff between quality and time solution / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T12:59:52Z (GMT). No. of bitstreams: 1 Sousa_VaniaNobrede_M.pdf: 984501 bytes, checksum: f58d5baf5c8e4dc8e704f4cb9aa47c6b (MD5) Previous issue date: 2006 / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T08:02:12Z (GMT). No. of bitstreams: 1 Andrade_CarlosEduardode_M.pdf: 1512396 bytes, checksum: aac3459428d8f61b130828587f727265 (MD5) Previous issue date: 2006 / Resumo: Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte / Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances / Mestrado / Mestre 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-09T00:31:09Z (GMT). No. of bitstreams: 1 Vignatti_AndreLuis_M.pdf: 1110014 bytes, checksum: 4a8c19589a3914eb255c6938623be094 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos a interação entre duas áreas: otimização combinatória e compartilhamento de custos (cost-sharing), que é a arte de dividir os custos associados a construção e manutenção de uma solução a qual um grupo de usuários é beneficiado. Apresentamos algoritmos para problemas de projeto de redes, tendo como objetivo principal os problemas ¿Connected Facility Location¿ e ¿Rent-or-Buy¿. Estes dois problemas são NP-difíceis, pois têm como caso particular o problema da arvore mínima de Steiner, que tambem é NP-dificil. Na primeira parte do trabalho, temos a seguinte questão como motivação: ¿Como projetar uma boa rede, ou seja, uma rede que satisfaça todas as propriedades do problema e ao mesmo tempo minimize o custo de construção desta rede?¿ 'E nesta parte que os algoritmos de aproximação entram em ação. Uma vez que esse custo for determinado, na segunda parte do trabalho, uma outra questão surge: ¿Como dividir esse custo entre todos os usuários que participam da rede de uma maneira ¿justa¿? Nesta parte, usaremos o compartilhamento de custos juntamente com as tecnicas de algoritmos de aproximação para responder a essa questão / Abstract: We consider the interplay of two areas: combinatorial optimization and cost-sharing in network design problems. In the first, we are interested to find a solution with small cost. In the second we would like to share the solution cost between its users. We present algorithms for the problems ¿Connected Facility Location¿ and ¿Rent-or-Buy¿. These two problems are NP-hard, since they have as a particular case the minimum Steiner tree problem, which is a known NP-hard problem. In the first part of this work, we have the following question as motivation: ¿how to design a good network, i.e., one that satisfies all problem requirements and minimize the overall network construction cost?¿ In this part, approximation algorithms takes action. Once this cost is determinated, in the second part of the work, another question arises: ¿How to distribute this cost among all users that participate in the network in a ¿fair¿ way? In this part, we will use cost-sharing together with approximation algorithms techniques to answer this question / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Orientadores: Carlos Alberto de Castro Junior, 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-14T21:34:08Z (GMT). No. of bitstreams: 1 Guimaraes_MarcosAntoniodoNascimento_D.pdf: 1387088 bytes, checksum: 36029ed51311645d24da08d56bb91409 (MD5) Previous issue date: 2009 / Resumo: O objetivo desse trabalho de pesquisa é desenvolver ferramentas computacionais eficientes para a otimização da operação de sistemas de distribuição de energia elétrica. A principal contribuição apresentada é fornecer uma metodologia para redução de perdas de potência ativa, baseada em reconfiguração e alocação de bancos de capacitores fixos e automáticos. É possível encontrar na literatura várias propostas baseadas nos mais diversos tipos de algoritmos, entretanto, na maioria dos casos as propostas apresentadas propõem o atendimento a um único objetivo. A proposta apresentada neste trabalho contempla a otimização dos objetivos de forma conjunta, usando um único algoritmo, de forma a tirar o máximo proveito dos recursos já instalados no sistema. Mostra-se que é possível obter uma economia significativa no custo de instalação de bancos de capacitores, utilizando a reconfiguração como ferramenta adicional. Um dos maiores desafios a ser enfrentado, no entanto, refere-se ao tamanho do espaço de busca, que nesse caso cresce consideravelmente. Para a resolução do problema optou-se pelo algoritmo genético, que é uma metaheurística já consagrada na resolução de problemas de grande complexidade. No decorrer do trabalho foram desenvolvidas diversas ferramentas e operadores genéticos especiais que tornaram possível a obtenção de excelentes resultados com baixo custo computacional. Adicionalmente, foi desenvolvido um algoritmo de Simulated Annealing que, a partir da melhor configuração obtida pelo algoritmo genético desenvolvido, otimiza as manobras dos taps do transformador da subestação de forma coordenada com taps dos capacitores automáticos. O comutador de tap do transformador tem uma vida útil limitada em aproximadamente 100.000 operações, o que corresponde a aproximadamente 30 operações diárias, e o algoritmo desenvolvido tem por finalidade, minimizar o número de operações diárias do dispositivo, prolongando sua vida útil. / Abstract: The goal of this research work is to develop efficient computational tools for optimizing the operation of distribution systems. The main contribution presented here is providing a methodology for reducing the real power losses based on reconfiguration and placement of both fixed and automatic capacitor banks. Many different methodologies, using several different algorithms can be found in the literature. However, most of them focus on one objective only. The method presented here comprises the simultaneous optimization of multiple objectives, in one algorithm only, to fully use the resources already installed in the system. It is shown that significant savings with the purchase of capacitor banks can be achieved by using reconfiguration as an additional tool. One of the hardest challenges to be tackled is related to the search space, that may grow significantly. The problem is solved by a genetic algorithms, which is an already widely accepted metaheuristic for solving very complex problems. Many different tools and special genetic operators have been developed along the research work. Those provided excellent results, at a low computational cost. Additionally, a simulated annealing algorithm was developed to optimize the substation transformer tap maneuvers in a coordinated way with the automatic capacitor bank tap maneuvers, from the best configuration obtained with genetic algorithms. The transformer tap commuter has a useful life limited to 100,000 operations, or approximately 30 daily operations. The proposed algorithm also minimizes the number of daily operations to stretch transformers' service life. / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-15T01:42:44Z (GMT). No. of bitstreams: 1 Gomes_LalinkadeCamposTeixeira_D.pdf: 3303378 bytes, checksum: 65adc8d5ec20cd1f431eaca2fe3765cc (MD5) Previous issue date: 2006 / Resumo: Problemas de otimização combinatória apresentam grande relevância prática e surgem em uma ampla gama de aplicações. Em geral, a otimização combinatória está associada a uma explosão de candidatos à solução, inviabilizando a aplicação de métodos exatos. Frente à intratabilidade desta classe de problemas via métodos exatos, nos últimos anos tem havido um crescente interesse por métodos heurísticos capazes de encontrar soluções de alta qualidade, não necessariamente ótimas. Considerando o notório sucesso empírico de meta-heurísticas concebidas através da inspiração biológica e na natureza, essas abordagens vêm ganhando cada vez mais atenção por parte de pesquisadores. É fato conhecido que não existe uma única metodologia capaz de sempre produzir os melhores resultados para todas as classes de problemas, ou mesmo para todas as instâncias de uma mesma classe. Assim, a busca de solução para problemas de natureza combinatória constitui uma linha de pesquisa desafiadora. Nesta tese são considerados problemas de otimização combinatória multicritério e multimodal. Como principal contribuição, destaca-se a concepção de novas meta-heurísticas para a solução de problemas combinatórios de elevada complexidade, tendo sido propostas duas classes de ferramentas computacionais. A primeira envolve um método híbrido fundamentado em mapas auto-organizáveis de Kohonen e inferência nebulosa, em que um conjunto de regras guia o processo de treinamento do mapa de modo a permitir o tratamento de problemas com restrições e múltiplos objetivos. A segunda abordagem baseia-se em sistemas imunológicos artificiais. Em particular, a abordagem imunológica levou à proposição de meta-heurísticas capazes de encontrar e manter diversas soluções de alta qualidade, viabilizando o tratamento de problemas multimodais. Como casos de estudo, foram consideradas duas classes de problemas de otimização combinatória multimodal: o problema de roteamento de veículos capacitados e o problema do caixeiro viajante simétrico. As técnicas propostas foram também adaptadas para a solução de problemas de bioinformática, em particular ao problema de análise de dados de expressão gênica, produzindo resultados diferenciados e indicando um elevado potencial para aplicações práticas. / Abstract: Combinatorial optimization problems possess a high practical relevance and emerge on a wide range of applications. Usually, combinatorial optimization is associated with an explosion of candidates to the solution, making exact methods unfeasible. Before the unfeasibility of exact methods when dealing with this class of problems, lately there has been an increasing interest in heuristic methods capable of finding high-quality solutions, not necessarily the optimal one. Considering the widely known empirical success of metaheuristics conceived with inspiration on biological systems and on the nature itself, such approaches are receiving more and more attention from the scientific community. Evidently, there is no single methodology able to always produce the best results for all classes of problems, or even for all instances of one specific class. That is why the search for solutions to combinatorial problems remains a challenging task. This thesis considers multicriteria and multimodal combinatorial optimization problems. As the main contribution, one can emphasize the conception of new metaheuristics designed to the solution of high-complexity combinatorial optimization problems, and two classes of computational tools have been proposed. The first one involves hybrid method based on Kohonen self-organizing maps and fuzzy inference, in which a set of rules guides the training of the self-organizing maps in order to allow the handling of problems with constraints and multiple objectives. The second approach is based on artificial immune systems. Particularly, the immune-inspired approach leads to the proposal of metaheuristics capable of finding out and maintaining multiple high-quality solutions, making it possible to deal with multimodal problems. As case studies, the capacitated vehicle routing problem and the symmetric traveling salesman problem are considered, giving rise to combinatorial and multimodal problems. The proposed techniques were also adapted to the solution of problems in the field of bioinformatics, specifically the analysis of gene expression data, leading to distinguished results and indicating a high potential for practical applications. / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T19:15:18Z (GMT). No. of bitstreams: 1 FrancaFilho_MoacirFelizardode_D.pdf: 1342634 bytes, checksum: 4855202b36314e8c55f20746c709054e (MD5) Previous issue date: 2007 / Resumo: Este trabalho é dedicado à programação de tarefas em máquinas paralelas. Dois ambientes são considerados. No primeiro, as máquinas são idênticas e o objetivo é a minimização da soma ponderada de custos de atraso. Todas as tarefas estão disponíveis para processamento no início do horizonte de programação e a cada uma são associadas uma data de entrega e uma penalização por atraso específicas. No segundo, as máquinas são não relacionadas e o objetivo é a minimização da soma ponderada de custos de avanço e de atraso. Instantes de liberação, datas de entrega, penalizações por avanço e por atraso são específicos para cada tarefa. Em ambos, as transições entre tarefas requerem tempos de preparação dependentes da seqüência de processamento. Os problemas são resolvidos por meio de GRASP e Busca Tabu. Memória de longo prazo é empregada para melhorar o desempenho das duas metaheurísticas. No GRASP, soluções de elite influenciam a fase construtiva. Na Busca Tabu, estratégias de diversificação e de intensificação fazem uso direto das soluções de elite e também de freqüências de residência. Como pós-otimização, nas duas metaheurísticas, realizam-se religações de caminhos entre as soluções de elite / Abstract: This work is dedicated to the scheduling of a set of jobs in parallel machines. Two scenarios are considered. In the first one, the machines are identical and the objective is the minimization of the weighted sum of tardiness costs. All jobs are ready for processing at the beginning of the scheduling horizon and to each one is associated a due date and a tardiness penalty. In the second scenario, the machines are non-related and the objective is the minimization of the weighted sum of earliness and tardiness costs. Ready times, due dates, earliness and tardiness penalties are specifics to each job. In both problems, the transitions between jobs require sequence dependent setup times. The problems are solved using GRASP and Tabu Search. Long term memory is applied to improve the performance of the metaheuristics. A set of elite solutions are used to influence the constructive phase in GRASP. In Tabu Search, diversification and intensification strategies make direct use of the elite solutions, as well of residence frequences. Path relinking between the elite solutions is used as a post-optimization approach / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-11T20:54:55Z (GMT). No. of bitstreams: 1 Meira_LuisAugustoAngelotti_D.pdf: 974332 bytes, checksum: 7097ff3ed310db70e5026afabc41ceb6 (MD5) Previous issue date: 2007 / Resumo: O trabalho desenvolvido neste doutorado consistiu em conceber algoritmos para uma série de problemas NP-dificeis sob a abordagem de aproximabilidade, complementado com resultados heurísticos e também de programação inteira. O estudo foi focado em problemas de classificação e particionamento em grafos, como classificação métrica, corte balanceado e clusterização. Houve um equilíbrio entre teoria e aplicabilidade, ao obterse algoritmos com bons fatores de aproximação e algoritmos que obtiveram soluções de qualidade em tempo competitivo. O estudo concentrou-se em três problemas: o Problema da Classificação Métrica Uniforme, o Problema do Corte Balanceado e o Problema da Localização de Recursos na versão contínua. Inicialmente trabalhamos no Problema da Classificação Métrica Uniforme, para o qual propusemos um algoritmo O (logn)-aproximado. Na validação experimental, este algoritmo obteve soluções de boa qualidade em um espaço de tempo menor que os algoritmos tradicionais. Para o Problema do Corte Balanceado, propusemos heurísticas e um algoritmo exato. Experimentalmente, utilizamos um resolvedor de programação semidefinida para resolver a relaxação do problema e melhoramos substancialmente o tempo de resolução da relaxação ao construir um resolvedor próprio utilizando o método de inserção de cortes sobre um sistema de programação linear. Finalmente, trabalhamos com o problema de Localização de Recursos na variante contínua. Para este problema, apresentamos algoritmos de aproximação para as métricas l2 e l2 2. Este algoritmo foi aplicado para obter algoritmos de aproximação para o problema k-Means, que 'e um problema clássico de clusterização. Na comparação ao experimental com uma implementação conhecida da literatura, os algoritmos apresentados mostraram-se competitivos, obtendo, em vários casos, soluções de melhor qualidade em tempo equiparável. Os estudos relativos a estes problemas resultaram em três artigos, detalhados nos capítulos que compõem esta tese / Abstract: We present algorithms for combinatorial optimization NP-hard problems on classification and graph partitioning. The thesis concerns about theory and application and is guided by an approximation algorithms approach, complemented with heuristics and integer programming. We proposed good approximation factor algorithms as well as algorithms that find quality solutions in competitive time. We focus on three problems: the Metric Labeling Problem, the Sparsest Cut Problem and the Continuous Facility Location Problem. For the Metric Labeling Problem, we proposed an O(log n)-approximation algorithm. In the experimental analysis, this algorithm found high quality solutions in less time than other known algorithms. For the Sparsest Cut Problem we proposed heuristics and an exact algorithm. We built an SDP Solver to the relaxed formulation using a semi-infinity cut generation over linear programming. This approach considerably reduces the time used to solve the semi definite relaxation compared to an open source semi definite programming solver. Finally, for the Continuous Facility Location Problem we present approximation algorithms to the l2 and l2 2 distance function. These algorithms are used to obtain approximation algorithms to the k-Means Problem, which is a basic clustering problem. The presented algorithms are competitive since they obtain in many cases better solutions in equivalent time, compared to other known algorithms. The study of these problems results in three papers, which are detailed in chapters that make this thesis / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T05:42:28Z (GMT). No. of bitstreams: 1 Scaraficci_RafaelAugusto_M.pdf: 1073556 bytes, checksum: 1831ea71ef0edfbf5da96e257b81bbfc (MD5) Previous issue date: 2008 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de planejamento e escalonamento de atividades de colheita e de transporte de madeira. Trata-se de um problema típico de grandes empresas do setor de celulose e papel. Ele consiste em planejar, para um horizonte de curto prazo, a colheita de madeira em diferentes áreas florestais e também o transporte da madeira colhida para uma unidade de produção de celulose e papel. O planejamento das atividades florestais considera um conjunto complexo de restrições operacionais, que envolvem, por exemplo, a organização das áreas florestais, propriedades da madeira cortada, a organização das equipes de colheita e a degradação das estradas com as chuvas. Neste projeto, desenvolvemos e analisamos algumas estratégias algorítimas híbridas baseadas em princípios da metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) combinada com elementos de memória de longo prazo, métodos de recombinação de soluções e também modelos lineares. Testes computacionais mostraram que nossas estratégias são robustas e capazes de produzir soluções de alta qualidade em um curto intervalo de tempo. / Abstract: This thesis aimed at studying and solving a planning and scheduling problem stemming from forest harvest and wood transportation activities. Our approach treated a real problem faced by large pulp and paper companies in Brazil. It consists in planning, for a short-term horizon, the harvesting operations in different forest areas and the transportation of the logs to a processing unit, while satisfying a complex set of constraints, which includes constraints related to the structure of the harvest areas, some properties of the logs, the organization of the harvest teams and the degradation of dirt roads during rainy periods. In this research, we developed and evaluated some hybrid algorithmic strategies based on some principles of the GRASP (Greedy Randomized Adaptive Search Procedure), combined with advanced techniques such as long term memory, solution recombination methods and linear models. Computational tests proved that our strategies are robust and able to produce high quality solutions in a short amount of time. / Mestrado / Mestre em Ciência da Computação