Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T00:16:31Z (GMT). No. of bitstreams: 1 Zilli_PetersonKatagiri_M.pdf: 1307926 bytes, checksum: 5fe0ddfca7cce84d9e26b66106d61e8b (MD5) Previous issue date: 2011 / Resumo: O Problema de Roteamento de Veículos (VRP, em inglês) foi proposto por Dantzig e Ramser em 1959 e, desde então, um grande número de artigos foi dedicado à solução de suas variantes. O problema original consiste em determinar rotas otimais que serão usadas por veículos de capacidade limitada para servirem a um conjunto de clientes. Neste trabalho focamos o estudo e a implementação dos modelos chamados de "ricos" na literatura, os quais englobam variantes complexas do VRP e conseguem representar situações mais próximas dos problemas logísticos encontrados em sistemas de distribuição reais. A principal motivação para esta pesquisa é uma aplicação prática referente ao problema de roteamento dos ônibus fretados pela UNICAMP para o transporte de seus funcionários, que se caracteriza como um modelo rico. O objetivo final é a otimização de tal processo através da minimização da distância total percorrida ou do número de veículos empregados, com a consequente redução dos gastos incorridos pela Universidade. Portanto, além do seu aspecto científico, esta dissertação produz resultados com chances reais de trazer benefícios à administração de uma instituição pública de ensino. Para que isto venha a ocorrer, as heurísticas desenvolvidas foram inseridas em um sistema de informações geográficas, que será usado pela universidade no processo de criação e otimização das rotas a serem licitadas publicamente / Abstract: The Vehicle Routing Problem (VRP) was first proposed by Dantzig and Ramser in 1959 and, since then, a large number of papers has been devoted to the solution of its variants. The original problem consists in determining an optimal set of routes to be used by vehicles of limited capacity that serve a set of customers. In this paper we focus on the study and implementation of models called "rich" in the literature, which include complex variants of the VRP that represent situations closer to the logistical problems encountered in real distribution systems. The main motivation for this research is a practical problem concerning the routing of buses chartered by UNICAMP for transporting a part of its employees, which is characterized as a rich model. The goal is to optimize this process by minimizing the total travel distance or the number of vehicles used, with a consequent reduction of the expenses incurred by the University. Therefore, in addition to its scientific aspect, this dissertation gives results with real chances to benefit the administration of a public university. For this to happen, the heuristics developed were entered into a geographic information system, which will be used by the university in the process of creation and optimization of routes to be publicly auctioned / Mestrado / Pesquisa Operacional / 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-08-19T04:31:47Z (GMT). No. of bitstreams: 1 Braga_AndreideAlmeidaSampaio_M.pdf: 1060769 bytes, checksum: 789d9000e49ebe5d5a54a275c6018cb6 (MD5) Previous issue date: 2011 / Resumo: O problema de particionamento de conjuntos (SPP, do inglês set partitioning problem) é considerado um dos problemas de otimização combinatória com mais vasta gama de aplicações. Para solucioná-lo, utilizam-se comumente métodos tradicionais para a resolução de problemas NP - Difíceis. Nesta dissertação, estuda-se o uso da combinação de relaxação Lagrangiana com planos de corte. Relaxação Lagrangiana é uma técnica que tem sido usada com bastante sucesso para atacar vários problemas NP-Difíceis. Os algoritmos relax-and-cut, em especial, onde se adicionam dinamicamente planos de corte a relaxações Lagrangianas, têm ganhado bastante destaque nas últimas décadas. Em [15], Cavalcante et al. aplicam um algoritmo relax-and-cut ao SPP e obtém ótimos resultados. No entanto, tal algoritmo, bem como implementações em geral da citada combinação, são ainda passíveis de refinamentos e extensões. O estudo proposto aqui é realizado por meio das seguintes extensões do referido algoritmo: a implementação de uma partida quente para o multiplicador de uma inequação adicionada; a incorporação do algoritmo a uma enumeração, gerando, assim, um branch-and-cut baseado em relaxação Lagrangiana para o SPP; a implementação do citado branch-and-cut com o emprego de relaxações alternativas e a implementação de uma versão distribuída do algoritmo / Abstract: The set partitioning problem (SPP) is considered one of the combinatorial optimization problems with the widest range of applications. To solve the SPP, one commonly uses traditional methods for NP-Hard problem solving. In this dissertation, we study the use of the combination of Lagrangean relaxation with cutting planes. Lagrangean relaxation is a technique that has been used quite successfully to tackle several NP-Hard problems. In particular, relax-and-cut algorithms, in which cutting planes are added dynamically to Lagrangean relaxations, have gained much importance in the last decades. In [15], Cavalcante et al. applied a relax-and-cut algorithm to the SPP and obtained promising results. However, that algorithm, as well as implementations of the mentioned combination in general, are still subject to refinements and extensions. The study proposed here is carried out through the following extensions of that algorithm: the implementation of a warm start to the multiplier of an added inequality; the incorporation of the algorithm to an enumeration, thus generating a Lagrangean relaxation based branch-and-cut for the SPP; the implementation of that branch-and-cut with the use of alternative relaxations and the implementation of a distributed version of the algorithm / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T10:47:23Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5) Previous issue date: 2011 / Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração / Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T17:20:46Z (GMT). No. of bitstreams: 1 Silva_FabricioLuisSantosda_M.pdf: 657410 bytes, checksum: 65ac7a297f6547a9ac70dfa42604f1ce (MD5) Previous issue date: 2010 / Resumo: Neste trabalho lidamos com o problema de Empacotamento em Faixa Bidimensional considerando o caso em que os itens devem ser dispostos de forma a manter o empacotamento estável e satisfazer uma ordem de descarregamento imposta. Consideramos o caso em que a orientação dos itens é fixa. Definimos uma metodologia para analisar a estabilidade do empacotamento observando as condições de equilíbrio estático para corpos rígidos. Desenvolvemos heurísticas e formulamos um programa linear inteiro para o problema de Empacotamento em Faixa sujeito a tais restrições. A resolução da formulação inteira ocorre através de uma estratégia do tipo branch-and-cut. As restrições de estabilidade foram inseridas como planos de corte de maneira a remover empacotamentos que não são estáveis. Em nossos experimentos computacionais, vemos que o modelo proposto é adequado para lidar com instâncias de pequeno até médio porte, dentro de um tempo computacional razoável / Abstract: This paper investigates the Two-Dimensional Strip Packing Problem considering the case in which the items should be arranged to form a stable packing and satisfy an order of unloading, so that after unloading, the packing is still stable. We consider the case where the items are oriented and rotations are not allowed. We present a methodology to analyze the stability of the packing observing the conditions for static equilibrium of rigid bodies. We present heuristics and formulate an integer linear programming model for the Strip Packing problem considering such constraints. To solve the integer formulation, we develop a branch-and-cut approach. For each integer solution obtained during the branch-and-cut algorithm, corresponding to a non-stable packing, we insert a cutting plane for which this integer solution is not satisfied. In our computational experiments, we see that the proposed model is suitable to deal with small and mid-sized instances. Some optimal solutions were obtained after few hours of CPU processing / Mestrado / Mestre em Ciência da Computação

Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T02:04:53Z (GMT). No. of bitstreams: 1 Biller_PrisciladoNascimento_M.pdf: 16893114 bytes, checksum: 4346a38c95f6bb748d840f487e61890b (MD5) Previous issue date: 2012 / Resumo: Os rearranjos são eventos evolutivos que alteram de diferentes formas a ordem de grandes segmentos do genoma. Explicar a história evolutiva de um conjunto de espécies com rearranjos pode ser visto como um problema de otimização computacional, chamado de Problema de Rearranjo de Múltiplos Genomas. Este problema consiste em encontrar uma árvore que relaciona o conjunto de genomas recebido, minimizando a soma dos pesos das arestas, sendo o peso de uma aresta o número de rearranjos que explica a evolução entre os genomas dos vertesses incidentes. A qualidade da inferência e a complexidade do problema dependem do modelo de rearranjo utilizado, que define formalmente como os genomas podem ser modificados. Recentemente, um novo modelo de rearranjo foi proposto, o Single-Cut-or-Join (SCJ), que traz como grande vantagem a simplificação de muitos problemas, que sob outros modelos são NP-difíceis. Apesar da teoria do SCJ ser bem construída, havia dúvidas sobre sua relevância biológica. Neste trabalho contribuímos com o entendimento deste modelo, realizando um extenso estudo que aplica o SCJ sob diferentes condições evolutivas, com dados reais e simulados, analisando dois aspectos da reconstrução evolucionária: a estrutura da árvore e o genoma (ordem dos genes) das espécies ancestrais. Na primeira análise, descobrimos que o SCJ é capaz de recuperar entre 60% e 80% da estrutura da árvore. Em relação à segunda questão, dada a estrutura da árvore, a reconstrução dos genomas ancestrais varia conforme a distância da espécie ancestral para as espécies conhecidas. No caso de espécies ancestrais mais próximas às folhas, cerca de 85% da ordem dos genes foi coberta enquanto, em espécies mais distantes, aproximadamente 50% da ordem dos genes foi coberta, usando conjuntos de genomas de 64 espécies. Em relação ao tempo, os métodos, que implementamos em Java, podem encontrar a topologia de 64 genomas com 2000 genes cada em cerca de 10,7 minutos e reconstruir seus genomas ancestrais em 0,05 minutos, ambos em um computador desktop padrão / Abstract: Rearrangements are evolutionary events that modify in different ways the order of large segments in genomes. To explain the evolutionary history of a set of species with rearrangements can be seen as an computational optimization problem, called Multiple Genome Rearrangement Problem. This problem consists in finding a tree which relates the set of genomes received, minimizing the sum of edge weights, where the weight of an edge is the number of rearrangements that explains the evolution between the genomes of incident vertices. The quality of the inference and complexity of the problem depend on the rearrangement model used, which formally defines how the genomes can be modified. Recently, a new rearrangement model was proposed, Single-Cut-or-Join (SCJ), which brings a significant advantage in simplifying many problems that are NP-hard under other models. Although the SCJ theory is well constructed, there were doubts about its biological relevance. In this work we contribute to the understanding of this model, performing an extensive study that applies the SCJ under different evolutionary conditions, with real and simulated data, analyzing two aspects of evolutionary reconstruction: the tree structure and the genome (gene order) of the ancestral species. In the first analysis, we found out that SCJ can recover between 60% to 80% of the tree structure. Regarding the second question, given a tree structure, the reconstruction of ancestral genomes varies according to the distance from ancestral species to the known species. In the case of ancestral species close to the leaves, about 85% of the gene order can be recovered while, in more distant species, about 50% of gene order are recovered, using genome sets of 64 species. As far as time is concerned, the methods we implemented can find a topology for 64 genomes with 2000 genes each in about 10.7 minutes, and reconstruct the ancestral genomes in about 0.05 minutes, both on a typical desktop computer / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador : Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T00:48:43Z (GMT). No. of bitstreams: 1 Costa_AlyssonMachado_M.pdf: 694166 bytes, checksum: 446bf3769d5078fa5450d0342397fc40 (MD5) Previous issue date: 2002 / Mestrado

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-03T14:28:12Z (GMT). No. of bitstreams: 1 Carvalho_RodrigoMoreira_M.pdf: 6710938 bytes, checksum: 15412b36523f97788649863056960796 (MD5) Previous issue date: 2002 / Resumo: A área de otimização combinatória multiobjetivo tem despertado crescente interesse pela sua importância prática e pela necessidade de desenvolver métodos eficientes que forneçam uma boa aproximação das soluções ótimas de Pareto. Neste trabalho é abordado o problema de seqüenciamento de tarefas em uma máquina com tempos de processamento dependentes da seqüência, datas de entrega e duas medidas de desempenho: soma do atrasos das tarefas e tempo total para processar todas as tarefas, também chamado de makespan. A minimização do makespan é equivalente à minimização do comprimento da rota no problema do caixeiro viajante assimétrico. Diversas heurísticas construtivas para cada critério propostas na literatura foram adaptadas para gerar um conjunto inicial de soluções não dominadas. Este conjunto é utilizado como partida em um método de busca em vizinhança com múltiplos recomeços. Vários tipos de vizinhanças foram testados, bem como diferentes estratégias de implementação de uma busca local multiobjetivo. Uma versão do método é testada em problemas pequenos, onde as soluções ótimas de Pareto são obtidas por enumeração completa. Para problemas grandes testa-se o desempenho relativo de diversas versões do método, e compara-se a qualidade das soluções que minimizam cada objetivo individualmente com a qualidade das soluções geradas por algoritmos mono-objetivos propostos recentemente na literatura / Abstract: The area of multio~ve combinatorial optimization has attracted the attention of researchers due to its practical importance and the need to develop efficient methods that yield a good approximation of the Pareto optimal solutions. This work addresses the sequencing of jobs in a single machine with sequence dependent setup times, due dates and two performance measures: the sum of job tardiness and the total time to process all jobs, also known as makespan. The minimization of the makespan is equivalent to the minimization of the tour length for the asymmetric traveling salesman problem. Several constructive heuristics proposed for each criterion in the literature were adapted to generate an initial set of nondominated solutions. This set is used to start a neighborhood search method with multiple restarts. Various neighborhood types were tested, as well as different strategies of implementing a multiobjective local search. A version of the method is tested for small problems, where the optimal Pareto solutions are obtained by complete enumeration. For larger problems, the relative performance of versions of the method is evaluated, and the quality of the solutions that minimize each objective is compared with the solutions generated by single-objective algorithms recently proposed in the literature / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T21:35:03Z (GMT). No. of bitstreams: 1 Yoshimoto_Eduardo_M.pdf: 1325962 bytes, checksum: 7a3d6ef896a0e63627f46cd396e917bc (MD5) Previous issue date: 2003 / Resumo: Este trabalho apresenta uma nova metodologia para o Problema de Planejamento de Redes Secundárias de Distribuição de Energia Elétrica. A metodologia visa a minimização dos custos através de métodos heurísticos de otimização, tendo o compromisso de atendimento da demanda do consumidor final. A metodologia foi desenvolvida para um cenário onde se planeja a construção de um novo loteamento ("greenfield"). Divide-se a metodologia em três etapas, utilizando-se técnicas formais de otimização baseadas em heurísticas construtivas e de melhoria. Inicialmente, localiza-se os transformadores, utilizando-se o método das p-medíanas. Em seguida, através do algoritmo de obtenção de caminhos mínimos, é feita a ligação dos consumidores finais aos transformadores. Por fim, utilizando-se de um problema de Steiner, é feito o condutoramento da rede primária aos transformadores. Esta divisão é a fase construtiva do método GRASP. Na fase de melhoria é aplicada uma Busca em Vizinhança Variável (VNS). O trabalho propõe também uma nova metodologia para consideração adequada dos requisitos de potência e energia nas redes. Estudos de casos detalhados ilustram a aplicação das metodologias propostas. / Abstract: This work presents a new methodology for the planning problem of secundary networks in power distribution systems. The approach aims to minimize the compromise between facility costs and technical losses in secundary systems. The metodology was mainly developed for greenfild problems, where a new network must be built completely. It comprises three main phases, based on formal optimization techniques and heuristics. The first phase deals with transformers alocation, using a p-median optimization model. The second phase solves the secondary network routing problem. Finally, a Steiner tree problem defines the connections of transformers with the existing primary network. The three phases comprise the constructive part of a Greedy Randomized Adaptive Search Procedures (GRASP). Following, a Variable Neighborhood Search (VNS) process is applied to improve the solution. The work also presents a new approach to deal with loads, separeting power and energy demands. Case studies illustrate the possibilities of the approach. / Mestrado

Orientadores : Carlos Magnus Carlson Filho, Raul Vinhas Ribeiro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T22:22:33Z (GMT). No. of bitstreams: 1 Sousa_MarcosAntoniode_D.pdf: 2731661 bytes, checksum: feeceb1fd383e3af6f8ce129bce5b0c6 (MD5) Previous issue date: 2004 / 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-03T23:44:20Z (GMT). No. of bitstreams: 1 Shiguemoto_AndreLuis_M.pdf: 3046317 bytes, checksum: c423cde2a2fa6c3581d15058afec5085 (MD5) Previous issue date: 2004 / Mestrado / Engenharia Eletrica / Mestre em Engenharia Elétrica