Made available in DSpace on 2018-09-11T12:28:07Z (GMT). No. of bitstreams: 1 tese_12118_Tese GIOVANNI 2018.pdf: 9554637 bytes, checksum: 1a8aa73adf768205b656d903813f23cc (MD5) Previous issue date: 2018-05-29 / A colheita e o transporte florestal são responsáveis pela maior parte dos custos da madeira posta no pátio das indústrias de celulose. Um planejamento eficiente poderá reduzir os custos de produção das empresas deste segmento. Neste sentido, a pesquisa operacional possui potencial para ser utilizada na solução, de forma ótima, de um problema recorrente nas empresas do setor florestal, que é a necessidade de eficiência na logística de transporte das máquinas florestais, de forma a evitar o máximo possível o tempo em espera para o transporte. Portanto, o objetivo deste trabalho é propor um modelo de programação e roteirização do transporte de máquinas florestais utilizando técnicas de pesquisa operacional. Trata-se de um problema multiobjetivo que busca determinar a rota de menor distância, o atraso mínimo possível e o número ideal de veículos para o transporte de máquinas florestais. O problema apresenta também restrições a serem atendidas, como horário específico para o transporte de cada máquina, frota heterogênea para atender as máquinas que possuem dimensões diferentes. A metodologia de modelagem baseou-se no problema de roteamento de veículos com coleta e entrega, janelas de tempo e frota heterogênea PRVCEJTFH com modificações para atender os objetivos deste estudo. Como método de solução foi utilizado o método exato por meio do algoritmo Branch and Bound. O modelo de otimização do transporte de máquinas florestais possibilitou encontrar uma solução ótima para determinar a rota de transporte com menor distância ponderada pela qualidade da estrada e minimizou o número de veículos pranchas utilizados no transporte das máquinas. Estas soluções têm relação direta com os custos associados ao transporte de máquinas florestais. Em situações de alta demanda da empresa o modelo minimizou o atraso. Nestas circunstâncias o gestor pode decidir por reduzir os atrasos independentemente do número de veículos necessários para o transporte das máquinas. Esta decisão deve ser tomada considerando aspectos econômicos e técnicos. O modelo proposto apresenta eficácia e eficiência, tornando possível obter a melhor solução possível em cada situação e em um tempo aceitável. Palavras chave: Planejamento, logística, otimização, pesquisa operacional, manejo florestal.

Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T10:33:41Z (GMT). No. of bitstreams: 1 Longo_HumbertoJose_M.pdf: 2296998 bytes, checksum: cb6cef9a3b19187ee26dc91e8fe15b17 (MD5) Previous issue date: 1995 / Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na funda­mentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação efici­ente entre vários algoritmos, para a resolução de problemas adequados à aborda­gem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algu­mas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil reso­lução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP / Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that fit in a multi-algorithm approach. Another goal of this work is an extensive study of the SCP which covers: the SCP structures its formulation as a 0-1 ILP; and the description of the main heuristic and exact methods currently available for its resolution. This study is most1y required since we are concerned with the development of a multi-algorithm method. The resulting software architecture makes use of approximate algorithms for the resolution of the se P and its continuous relaxation dual. This primal-dual approach guarantees the best found solution to be at a certain percentage of the optimal solution and, eventually, proves the solution optimality. The main components of the proposed architecture are greedy and consensus algorithms, tabu search procedures, subgradient methods and cutting plane generators. The main exact methods for the se P resolution are based on enumerative methodologies. Most of these methods deploys many of the heuristic technics used in the proposed architecture to the enumeration scheme. However, these methods have a poor performance in some instance classes, because they do not obtain good solutions in a reasonable time limit. The proposed architecture was applied to particularly hard instances. The obtained results show that it is possible to reach solutions, at an acceptable computational effort, that are at least comparable to the ones obtained by the best algorithms for the SCP / Mestrado / Mestre em Ciência da Computação

Orientador: Hermano M. F. Tavares / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-21T16:17:49Z (GMT). No. of bitstreams: 1 Bortolon_Saulo_D.pdf: 69317158 bytes, checksum: c5903a7e514f801574ccbb85ad636f39 (MD5) Previous issue date: 1996 / Resumo: A Rede de Transporte (RT) compreende todos os sistemas responsáveis pela comunicação entre centros de fios de uma rede de telecomunicações. É talvez a porção da rede que mais rapidamente incorpora inovações tecnológicas à medida que estas alcançam o mercado. Também é uma das partes das redes de telecomunicações onde mais tradicionalmente se usam ferramentas de otimização matemática ao se efetuarem estudos de planejamento. Nos últimos anos a RT vem sendo revolucionada pela introdução da Hierarquia Digital de Transmissão Síncrona (SDH), que viabiliza o emprego de altíssimas taxas de transmissão e de topologias inovadoras, das quais destacam-se os anéis auto-regeneradores e do hubs (roteadores). Estas novas opções tornam obsoletas as técnicas de planejamento hoje existentes, fazendo-se necessárias novas metodologias para o projeto de redes SDH. Neste sentido, propõe-se aqui uma metodologia de planejamento para redes de transporte SDH baseada em modelos de otimização matemática. Especificamente, propõe-se modelos de Programação Linear Inteira Mista que tratam a Rede de Transporte como uma rede de fluxo multiproduto, com custos associados a componentes modulares. A metodologia prevê um alto grau de interação com planejador ao longo do processo de planejamento, o que a faz adequada a sistemas computacionais de suporte à tomada de decisão... Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: The Transport Network - TN - is the part of a Telecommunications Network that provides connections between central offices. Probably, this is the part of the communications network that first incorporates any technological evolution. At least, that?s what happened with voice digitalization and optical transmission. The transport network is also a network where opmitization techniques are traditionally used during planning studies. In recent years the TN has been the prefereable place for introduction of the Synchronous Digital Hierarchy (SDH), that enables to use very high transmission bit-rates on innovative network topologies. Among those, self-healing rings and chains topologies have been widely used. Those new network topologies and transmission rates have led the existing planning methodologies to obsolescence. This work proposes a new planning methodology to SDH transport network, along which several optimization techniques are used. Mixed Integer Linear programs are used to model the SDH transport network as a multicommodity flow network, with modular capacities associated with its arcs and nodes. The proposed methodology permits several interactions between network planners and the optimization models along the planning process. These optimization / interaction based approach makes the methodology very appealing to computer-based decision support systems... Note: The complete abstract is available with the full electronic digital thesis or dissertations / Doutorado / Doutor em Engenharia Elétrica

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

Orientador: Celio Cardoso Guimarães / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T17:14:53Z (GMT). No. of bitstreams: 1 Nanni_EdicezarLeandro_M.pdf: 5558031 bytes, checksum: 1f46f7a5fa8950b399bcbe31efc2b68d (MD5) Previous issue date: 1998 / Resumo: Log-structured File Systems, ou LFS, são sistemas de arquivos que possuem alto desempenho em ambientes de engenharia, escritórios e ensino, pois organizam os dados na forma de um log no disco. Seu alto potencial de aumento de desempenho provém da eliminação de grande parte dos posicionamentos do braço do disco (seeks) nas escritas e do uso tradicional de processadores e memória cache nas leituras. Nesta dissertação, a estrutura do LFS é examinada em detalhes, analisando-se as suas duas principais implementações [ROS92a, SEL93a], e comparada com o sistema de arquivos tradicional do UNIX, o FFS [MCK84], no que diz respeito à organização dos dados, funcionamento e desempenho. As vantagens e desvantagens do LFS em relação ao FFS também são apresentadas. Diversos aspectos de sistemas de arquivos, como tecnologias de hardware, cache de dados e a camada VFS (Virtual File System) [KLE86] são analisados. Neste trabalho, apresentamos a construção de um protótipo de um LFS no sistema operacional LINUX. Para este fim, utilizamos a ferramenta UserFS [FIT93], que possibilita a processos de usuário responderem às chamadas de sistema normalmente feitas apenas ao código do sistema de arquivos implementado no núcleo do sistema operacional / Abstract: Log-structured File Systems (LFS) have high performance in workloads found in offices, engineering and educational environments, due to the physical data organization in a log, i.e., a sequential area in the disk. It's high potential for performance improvements come from the elimination of disk seeks in write operations and the traditional use of processors and memory cache in read operations. This dissertation examines in detail the structure of LFS and compares it to the traditional UNIX Fast File System (FFS) [MCK84], with respect to physical data organization internal workings and performance. The two main known LFS implementations [ROS92a, SEL93a] are also reviewed and compared. Many file system aspects such as hardware technologies, cache memories and the Virtual File System (VFS) [KLE86] are also examined. In this work we built a LFS prototype for the LINUX operating system. For this purpose we have used the UserFS tool [FIT93]. This tool allows a use r process to act on system calls usually handled by file system code inside the operating system kernel / 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