Orientador: Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-21T19:37:43Z (GMT). No. of bitstreams: 1 VelezBenito_RafaelCarlos_D.pdf: 8351475 bytes, checksum: c7d4a0617510bde9ca9da88e7d103edb (MD5) Previous issue date: 1996 / Resumo: O presente trabalho faz um estudo cuidadoso dos métodos de pontos interiores para obter implementações eficientes na solução de problemas de fluxo de custo mínimo. Tendo em vista que a maior parte do esforço computacional dos algoritmos baseados nos métodos de pontos interiores é dedicado à solução de sistemas do tipo AD* ATY = b, é feita uma análise deste sistema, explorando-se as características da estrutura de redes. Implementa-se especializações dos métodos diretos e dos métodos iterativos. Os métodos diretos são especializações da decomposição de Choleski. Heurísticas do tipo grau mínimo e preenchimento local mínimo são usadas para reordenação das linhas e colunas, procurando conservar a esparsidade da matriz AD* AT. Para a família dos problemas de transportes e atribuição, desenvolve-se um método de ordenação ótima. Os métodos iterativos são do tipo gradiente conjugado pré-condicionado. A estrutura de rede permite agilizar o cálculo das direções, reduzir requisitos de memória e construir pré-condicionadores bem informados. Um pré-condicionador do tipo diagonal é usado nos primeiros passos dos métodos de pontos interiores. Quando a solução se aproxima da otimalidade, constrói-se um outro pré-condicionador, baseado em estimações sobre a base ótima. Desenvolve-se implementações especializadas à problemas de fluxo de custo mínimo dos métodos primal afim, dual afim, primal dual e preditor-corretor. Interpretações baseadas no método de Newton para solução de problemas não lineares levaram a inovações nas implementações dos métodos afins. Estuda-se o problema de falta de volume (ou falta de pontos interiores), aspecto frequente em problemas de fluxo de custo mínimo. Avalia-se suas conseqüências na utilização de métodos de pontos interiores. A partir dos experimentos computacionais com os códigos desenvolvidos, procura-se fazer uma sistematização dos problemas em classes, com indicação das melhores alternativas de solução para cada classe.Finalmente, faz-se extensões das idéias desenvolvidas para a resolução de problemas de fluxos generalizados, através de métodos de pontos interiores / Abstract: This work is a careful study of the interior point methods looking for eflicient implementations for network flow linear programs. Computational experiments are developed with the primal afline, dual afline, primal dual and predictor-corrector methods looking for the best alternatives for different classes of problems. We discuss Newton's method interpretations of these methods. Since most of the computational time of the interior point methods is spent solving systems of the type (AD* AT)y = b, for different diagonal matrices D* and the same incidence matrix A we take advantage of the structure of such systems for networks. We use the sparse Cholesky factorization with two heuristics: the minimum degree and local minimum fill-in. For the family transportation and assignment problems, it is developed an optimal ordering method. We also use the conjugate gradient method with diagonal and maximum spanning tree preconditioners. We give particular attention to the degenerescency phenomena mainly to the lack of primal and/or dual interior feasible points. We study their consequences to interior point methods. Finally proposes extensions of the main ideas to the generalized network problems / Doutorado / Doutor em Engenharia Elétrica

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T19:24:13Z (GMT). No. of bitstreams: 1 Barboza_EduardoUchoa_M.pdf: 2477337 bytes, checksum: a3047f5638be88ee13e8e89477e4f570 (MD5) Previous issue date: 1997 / Resumo: A classificação de dados consiste em separar um conjunto de objetos, descritos por um conjunto de dados, em classes, de forma a que objetos na mesma classe sejam semelhantes entre si. A classificação freqüentemente é usada como uma ferramenta de pesquisa científica. Os objetivos de uma classificação podem diferir de acordo com as necessidades e com a origem dos dados sobre os objetos a classificar. Em alguns contextos existe interesse em associar os objetos aos vértices de um grafo, de forma que a semelhança entre os objetos esteja relacionada a proximidade nesse grafo. Os métodos existentes, para aplicações nestes contextos~ obrigam cada classe a formar um único componente conexo dentro do grafo. Chamamos essa abordagem de conexidade estrita e propomos a idéia de classificação com conexidade flexibilizada, ou seja a concepção de métodos que permitam a um usuário especificar o número de componentes de cada classe no grafo e mostramos porque essa flexibilização é desejável. Em seguida, estudamos a resolução de um problema computacional resultante da flexibilização da conexidade, o Problema da Atribuição ?-Conexa (PAgC). Demonstramos a NP-completude desse problema e apontamos alguns casos polinomiais. Então, concentramo-nos no estudo de diferentes formas para modelar matematicamente a conexidade flexibilizada. Os resultados obtidos podem ser naturalmente aplicados a outros problemas onde tal conexidade é necessária. Finalmente, propomos dois algoritmos para resolver (PAgC). Um baseado na técnica de branch-and-bound e outro na de branch-and-price. Uma comparação dos resultados obtidos por cada técnica é apresentada na seqüência. em estudo de classes de desigualdades válidas, capazes de melhorar substancialmente ambos os algoritmos, conclui a dissertação. / Abstract: Classification of objects amounts to defining, say, K clusters on a set of N objects such that object in a same cluster are alike. Classification is often used as a tool for scientific research. Some important contexts of objects classification use enhanced methods where the objects are associated to vertices of a graph. Proximity between two objects in this graph usually means that the dissimilarity between them is small. The methods applied in such contexts require each cluster to define a single connected component on this graph. We call this strict connectivity approach and we propose the idea of flexible connectivity. This suggests the development of methods where the user may specify the number of connected components each cluster may form on the graph. We present reasons for this flexibilization. Next, we study the computational problem derived from the flexible connectivity, the y-Connected Assignment Problem (PAgC). We show this problem to be NP-complete and we point out some polynomial cases. Then, we concentrate our effort on deriving formulations for considering this flexible connectivity. Clearly, the conceived models can be applied to other problems where connectivity constraints are to be considered. Finally, we propose two algorithms to solve PAgC. One based on the branch-and-cut technique and other on the branch-and-price technique. A comparison between the results obtained with each technique is presented. We conclude this work studying classes of valid inequalities capable of improving the efficiency of both algorithms. / Mestrado / Mestre em Ciência da Computação

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T12:26:09Z (GMT). No. of bitstreams: 1 Nunes_AminadabPereira_M.pdf: 3033083 bytes, checksum: 00558771e9828bf4eaf6bf7d04026453 (MD5) Previous issue date: 1997 / Resumo: Seja P um conjunto finito de pontos no plano e S(P) o conjunto de todos os segmentos de reta com extremos em P. Uma triangulação planar de P é um subconjunto maximal de S(P) tal que nenhum par de segmentos neste subconjunto se intercepta, exceto possivelmente nos extremos. Chamamos de triangulação de custo mínimo a triangulação planar cuja soma total dos comprimentos de seus segmentos de reta é mínimo dentre todas as triangulações planares de P. Não se conhece algoritmo polinomial que resolva o problema de determinar a triangulação de custo mínimo de um conjunto de pontos no caso geral, contudo, também não está provado tratar-se de um problema NP-difícil. Neste trabalho estamos interessados na resolução exata deste problema. Nossa abordagem é baseada em técnicas de programação inteira, em particular estudamos duas formulações distintas para o problema. A primeira formulação é baseada em uma equivalência entre o problema da triangulação de custo mínimo e uma versão restrita do problema do conjunto independente em um grafo. Além das desigualdades obtidas através da observação desta equivalência, mostramos como fortalecer a formulação através de certas propriedades geométricas do problema. Estudamos ainda uma outra formulação baseada principalmente no trabalho apresentado por Loera et. al em [dLHSS96]. Enquanto na primeira formulação as variáveis binárias estão associadas aos segmentos em S(P), nesta segunda formulação as variáveis binárias estão associadas aos triângulos com vértices em P. Os resultados computacionais que obtivemos mostram uma clara superioridade do segundo modelo. Para a primeira formulação implementamos um algoritmo branch-and-cut que nos permitiu resolver problemas de até 160 pontos (|P| = 160). Já para a segunda formulação a solução ótima da relaxação linear sempre foi inteira, o que nos permitiu resolver instâncias com até 1000 pontos (|P| = 1000) / Abstract: Let P be a finite set of points in the plane and S(P) be the set of all segments with both extreme points in P. A planar triangulation of P is a maxirnal subset of S(P) such that no pair of segments is this subset intercept each other, except possibly at their extremities. A minimum triangulation of P is a planar triangulation whose sum of the lengths of all its segments is minimum over all possible triangulations of P. No polynomial algorithm is known that solves this problem in the general case, however it is also not known if the problem is NP-hard. In this work we are interested in solving the problem exactly. Our approach is based on integer programming techniques and is particular we have studied two different formulations for the problem. The first formulation is based on an equivalence between the problem of finding a minimum weight triangulation of P and a restricted version of the maximum independent set of a graph. Besides the inequalities arising from this observation, we show how to strength the formulation by using geometric properties if the problem. We also have studied a second formulation mainly based on the work of Loera et. al [dLHSS96]. While in the first formulation the binary variables are associated to the segments in S(P), in this second formulation the binary variables are associated to the triangles with vertices lying in P. Our computational results have shown that the second model clearly outperforms the first one. For the first formulation, we have implemented a branch-and-cut algorithm which allowed us to solve instances with up to 160 points (IPI = 160). On the other hand, for the for second formulation, the optimal solution of the linear relaxation was integer for all tested instances, which has made possible the solution of instances with up to 1000 points (IPI = 1000] / Mestrado / Mestre em Ciência da Computação

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T17:05:18Z (GMT). No. of bitstreams: 1 Martins_MarceloMeireles_M.pdf: 2721812 bytes, checksum: 510547006b1b6cd86f873c47547b0147 (MD5) Previous issue date: 1998 / Resumo: Normalmente, a abordagem econômica formula o problema de como determinar preços como um problema de otimização em que uma função de bem-estar social, representando a agregação das utilidades individuais, tem que ser maximizada. De outro lado estão as técnicas de engenharia, em que o controle do congestionamento de redes, que operam em escalas de tempo da ordem de meses, é obtido pela ampliação da capacidade. Esse problema é formulado, também, como um problema de otimização em que se busca definir a capacidade dos canais para se obter a otimização de uma função de performance. Esta dissertação mostra que para manter uma rede de computadores que oferece o serviço de chaveamento de pacotes, sem conexão, como é o caso do protocolo IP, funcionando dentro da especificação de performance para a qual foi projetada deve-se realizar a ampliação da capacidade sendo que o investimento necessário é dado pelo preço sombra do problema de otimização formulado para o projeto da rede. Mostra, também, que o problema do projeto de redes e de economia são complementares e podem ser relacionados através de uma função de performance. Mostra ainda que, sob certas condições, as soluções de um problema é válido para o outro e, portanto, as abordagens são tais que contribuirem uma com a outra na consecução dos seus objetivos. Um survey, até então inexistente, das propostas de tarifação para rede do tipo que estamos lidando, também é fornecido. / Abstract: With the on-growing demand for access and for use of computer networks, research takes place to find ways to control or to avoid congestion when the network, given its physical limitations, is unable to accomodate the excessive traffic. In this dissertation, we examined a parallel between the engineering approach, which offers the connectionless switching packets service (as it is the case of IP protocol), and the economic approach, which is concerned with the best way of allocating limited resources for a certain population of consumers. By using the optimization problems formulated in each case, it was possible to show that, to maintain a computer network functioning inside the performance specification, for which it was projected, the necessary investment to expand its capacity in the long run (time scale of months) is given by the shadow price of the optimization problem of its project. It also shows that the economic problem and the problem formulated for network projects may be related through a performance function. Moreover, it shows that, under certain conditions, the solution to the economic problem is also a solution to the problem of the network project and, therefore, the pricing may be used as instruments to the control of the congestion. A survey of the pricing proposals for networks or the type with which we are working is also suplied. / Mestrado / Mestre em Ciência da Computação

Orientadores : Anesio dos Santos Jr., Leonardo Nepomuceno / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T05:41:27Z (GMT). No. of bitstreams: 1 Tognete_AdrianaLuiza_D.pdf: 1108463 bytes, checksum: f28b6361a11d640064724f00eea15139 (MD5) Previous issue date: 2002 / Doutorado

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-02T14:09:48Z (GMT). No. of bitstreams: 1 Christofoletti_LucianoMarcelo_M.pdf: 330664 bytes, checksum: 72ba00623f07b0d6a740c86049e839b1 (MD5) Previous issue date: 2002 / Mestrado

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T19:57:30Z (GMT). No. of bitstreams: 1 Teodoro_AlanAugusto_M.pdf: 1993309 bytes, checksum: eb9abfe2294e3e44de68abc5fba42be3 (MD5) Previous issue date: 2003 / Resumo: Neste trabalho é realizado um estudo experimental de técnicas de otimização para gerar soluções eficientes para o problema do corte bidimensional, que pode ser definido como: dado um número finito n de itens retangulares de largura li, comprimento Ci e demanda di, a serem obtidos de retângulos maiores de dimensão LxC, encontrar padrões de corte que atendam a uma demanda de itens utilizando o menor número possível de retângulos maiores. O problema foi formulado através de um modelo de programação linear inteira. Para obter soluções de custo reduzido para o problema, aplicamos o método de geração de colunas, obtendo então soluções viáveis para o problema relaxado do programa linear inteiro. Utilizamos um algoritmo de aproximação para obter uma solução inicial de qualidade e métodos de arredondamento com tratamento de problema residual para transformar a solução fracionária em soluções viáveis para o problema. Finalmente, diversos estudos são realizados através de testes computacionais / Abstract: In this work we describe an experimental study of optimization techniques to generate efficient results for the two-dimensional cutting stock problem which can be defined as follows: given a finite number n of rectangular items of width li, length Ci and demand di, to be cut from larger rectangles with dimensions LxC, find cutting pattems which attend the demand of the requested items minimizing the number of larger rectangles. The problem is formulated as an integer programming mode!. To obtain solutions with reduced cost to the problem, we apply the column generation method, obtaining feasible solutions for the relaxed integer programo We use an approximation algorithm to generate a good initial solution and rounding techniques with treatment of the residual problem to transform the fractional solution into feasible solutions to the problem. Finally, several studies are realized through computational experiments / Mestrado / Engenharia de Computação / Mestre em Computação

Orientador: Rafael Santos Mendes / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Conputação / Made available in DSpace on 2018-07-25T01:26:28Z (GMT). No. of bitstreams: 1 Portugal_DeniseSoderoVinhas_M.pdf: 4601014 bytes, checksum: 6c5d47e08ef85485b21b3c75f560cb1d (MD5) Previous issue date: 1999 / Resumo: Um problema de escalonamento cíclico com recursos disjuntivos e múltiplos jobs, denominado job shop cíclico com jobs distintos, é investigado. Para a resolução deste problema duas modelagens em programação inteira mista são adaptadas de modelos encontrados na literatura. Os modelos são implementados no software GAMS. O comportamento dos modelos face a múltiplos variações paramétricas é analisado graficamente. Finalmente a equivalência entre os modelos é mostrada analítica e empiricamente / Abstract: A cyclic scheduling problem with disjunctive resources and multiples jobs called cyclic job-shop with differents jobs is investigated. The adaptation of two models in mixed integer programming, found in the literature, solve the problem. The models are implemented using software GAMS. The behavior of the models in face of multiple parameter variations is shown graphically. Finally the equivalence between models is shown analytically and empirically / Mestrado / Mestre em Engenharia Elétrica

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas. Instituto de Computação / Made available in DSpace on 2018-08-04T04:16:19Z (GMT). No. of bitstreams: 1 Ganhoto_MarcoAlves_M.pdf: 1370660 bytes, checksum: 851eb09fb46a8ed3bfb7990592eb9a41 (MD5) Previous issue date: 2004 / Resumo: Neste trabalho, investigamos abordagens para problemas de roteamento, que têm como finalidade encontrar um melhor conjunto de rotas para que veículos possam transportar mercadorias a clientes geograficamente dispersos, respeitando certas restrições, como por exemplo, a de capacidade de carga dos veículos. Para isto, além de pesquisas em diversas fontes de informações, desenvolvemos um aplicativo para auxiliar no entendimento dos algoritmos, na ilustração do texto e na realização de experimentos. A partir de observações feitas durante as execuções do aplicativo, experimentamos combinações de critérios de seleção de localidades, utilizando tais combinações durante a realização dos movimentos de intercâmbio de vértices entre rotas de uma conhecida estratégia, a Metaheurística Busca Tabu. Foram combinados critérios baseados em distâncias com critérios baseados em ângulos, para compor algoritmos que foram testados com instâncias clássicas utilizadas por diversos pesquisadores. Os resultados obtidos foram apresentados juntamente com os de outras estratégias, fornecendo valores iguais ao melhor valor conhecido para duas instâncias, e valores intermediários para as outras cinco instâncias utilizadas nos testes / In this work, we examine some approaches for vehicle routing problems, to find a best set of routes to enable companies for delivery goods or commodities to customers, respecting some constraints, such as vehicles loading capacity. To this purpose, besides researching available information sources, we have developed a software to help us to understand the algorithms issues, for enriching the text with illustrations, and for effectiving some experiments concerning to previously selected approaches. From the analysis made during running software process, we decided to arrange chosen vertices criterias, using these arrangements in the vertices interchanging movements between routes of an already know method, the Tabu Search Metaheuristic. More precisely, we have combined distances and angles criteria, to implement algorithms on which it were tested using some classical instances considered by several researchers. The obtained results are presented with those selected approaches, and it provided us two equals values to the best known solution, and five intermediate values amoung to the others used on these experiments / Mestrado / Engenharia de Software / Mestre Profissional em Computação

Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T09:04:57Z (GMT). No. of bitstreams: 1 Peixoto_HelvioPereira_M.pdf: 4847864 bytes, checksum: 5c12c6f491a25c85cdd5a524c7aa92e8 (MD5) Previous issue date: 1995 / Resumo: Times Assíncronos perfazem uma nova técnica de resolução aproximada de problemas, baseada na utilização simultânea de diversos algoritmos heurísticos, que cooperam entre si de maneira sinérgica, encontrando soluções ótimas ou quase ótimas, as quais não seriam encontradas pelos mesmos algoritmos quando executados isoladamente. Esta nova técnica tem sido aplicada com sucesso a problemas combinatórios de grande porte. O tema central deste trabalho é o desenvolvimento de uma metodologia de especificação de TImes Assíncronos, em particular para os problemas de Otimização Combinatória de uma única função objetivo, tendo em vista a não existência de trabalhos neste sentido. O objetivo é fornecer uma seqüência de passos e sugestões que venham a facilitar e agilizar a concepção e implementação de Times Assíncrono&. Como um exemplo de aplicação da metodologia proposta, abordou-se o problema clássico de escalonamento de tarefas Flow Shop Problem de permutação, para o qual foram especificados e implementados Times Assíncronos. Os resultados obtidos por esses Times Assíncronos sobre as instâncias testadas foram tão bons quanto ou superiores às melhores soluções conhecidas. Esses testes foram efetuados de forma paralela, mostrando uma aceleração linear na obtenção dos resultados, conforme o número de processadores utilizados. Além dos Times Assíncronos para o Flow Shop Problem, desenvolveram-se novas fórmulas para cálculo de limites inferiores, demonstrando, assim, a otimalidade de algumas soluções obtidas e melhorando os limites inferiores conhecidos de dezenas de outras instâncias. / Abstract: Asynchronous Teams (A-Teams) are a new problem resolution technique that uses simultaneously various heuristic algorithms. These algorithms cooperate synergically one with the other to find optimal or nearly optimal solutions that would not be found through isolated algorithms. This technique has been successfully applied to large combinatorial problems. The main objective of this work is the development of a methodology to specify Asynchronous Teams to Combinatorial Optimization Problems with one objective function, since there is no literature about that. The purpose is to generate a sequence of steps and suggestions making the conception and implementation of Asyncbronous Teams easy and quick. As an example of the proposed methodology, Asynchronous Teams were specified and implemented to the classical permutation Flow Shop Problem. The results obtained by these A- Teams over the tested instances were equivalent or better than those published as the best known values. These A- Teams were executed in a parallel computer, showing linear speed up in the number of processors. Not on1y were the A- Teams to FSP developed, but do were two new formulas to calculate lower bounds. These lower bounds proved the optimally of two instances and improved the lower bounds of many others. / Mestrado / Mestre em Ciência da Computação