Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T11:40:25Z (GMT). No. of bitstreams: 1 Macambira_ElderMagalhaes_M.pdf: 3883760 bytes, checksum: 901048c885d22ea3a00674f4c248ef9b (MD5) Previous issue date: 1997 / Resumo: Esta dissertação dá ênfase à abordagem poliedral para a resolução exata do Problema da Clique .Máxima com Peso nas Arestas. Dado um grafo completo não-dirigido Kn = (Vn, En), onde |Vn|= n, com um peso Cij associado a cada aresta (i,j) ? En, e um inteiro b, onde b = n; procuramos uma clique C em Kn cuja sorna dos pesos das arestas em C seja máxima e |C| = b. São apresentadas e discutidas diferentes formulações de programação linear inteira para o problema. Investigamos ainda a estrutura facial do poliedro associado ao problema realizando urna revisão bibliográfica das desigualdades conhecidas e introduzindo novas famílias de facetas. Por último, descrevemos os experimentos computacionais realizados com um algoritmo branch-and-cut e com urna metaheurística, ambos propostos neste trabalho. As maiores instâncias resolvidas de forma exata para este problema na literatura referem-se a grafos completos com no máximo 30 vértices. Neste trabalho, resolvemos exatamente instâncias para grafos com até 48 vértices e mostramos a força computacional para as novas desigualdades que introduzimos. / Abstract: Given a complete non-directed graph Kn = (Vn, En) on n nodes with weights on the edges and an integer b = n, we look for a clique C in Kn whose sum of the weights of the edges in e is maximum and such that |C| = b. We discuss on different integer programming formulations and investigate the facial structure of the polyhedron associated to the problem. New families of facet defining inequalities are introduced. Finally we describe our computational experiments with a branch-and-cut algorithm and a metaheuristic that we have proposed. The largest instances that are solved exactly in the literature refer to complete graphs with at most 30 nodes. In this work we solve to optimality instances for graphs with up to 48 nodes and we show the computational strength of the new inequalities we have introduced. / Mestrado / Mestre em Ciência da Computação

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-07-27T01:55:40Z (GMT). No. of bitstreams: 1 Bueno_EdilsonAparecido_M.pdf: 2749662 bytes, checksum: 4aed2eedc35e7de920f72fc065f5d3d7 (MD5) Previous issue date: 2000 / Resumo: Em sistemas de energia elétrica, continuamente ocorrem perdas, devido à resistência elétrica nas linhas e equipamentos. Estima-se que 7% de toda a energia elétrica gerada em sistemas de potência são perdidas, sendo 2% na transmissão e 5% na distribuição. O problema de minimização de perdas procura encontrar uma configuração da rede onde o montante das perdas seja reduzido. Este trabalho propõe um procedimento que combina técnicas para otimização de fluxos em redes com funções não lineares com o método GRASP para otimização combinatória. GRASP é um método iterativo que combina um método construtivo com busca local. Na fase de construção, cria uma solução viável, combinando uma função gulosa com seleção aleatória. Na fase de busca local, procura melhorar a solução. A estrutura da rede de distribuição de energia elétrica é usualmente radial. Inicialmente, relaxa-se a restrição de operação radial, encontrando-se uma solução otimista (limitante inferior) para o problema. Informações sobre os valores dos fluxos nos arcos da solução otimista são utilizadas para abrir chaves, guiando a fase de construção do método GRASP para encontrar soluções factíveis de boa qualidade. A busca local procura obter reduções adicionais de perdas através do método de troca de ramos. Estudos de casos ilustram as possibilidades da abordagem / Abstract: Energy is continuously dissipated in electric power systems due to electrical resistance in the lines and equipment. Losses amount to around 7% of total energy production, 2% in transmission and 5% in distribution. The problem of loss minimization tries to find a network configuration where the amount of losses is reduced. This work proposes a procedure that combines non-linear network flow optimization techniques with the GRASP method. GRASP is an iterative method that uses a combination of a constructive procedure with a local search. The construction phase obtains a feasible solution, combining a greedy function with a randomize selection. The local search tries to improve the solution. The structure of the electric power distribution network usually has a radial configuration. Initially, the constraint of radial operation is relaxed, meeting an optimistic solution (a lower bound) for the problem. Information from are flows in the optimistic solution are used to open switches, guiding the construction phase of GRASP to find feasible and good quality solutions. The local search tries to get additional reductions of losses through the branch-exchange procedure. Case studies iIIustrate the possibilities of the approach / Mestrado / Mestre em Engenharia Elétrica

Orientador : Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T19:54:03Z (GMT). No. of bitstreams: 1 Rodrigues_MaikolMagalhaes_M.pdf: 4069676 bytes, checksum: b0b8e4bc9cdbe5bfc3fb90f34a46b43e (MD5) Previous issue date: 2001 / Resumo: Este trabalho de mestrado procurou estudar e resolver o problema de planejamento de viagens de linhas de ônibus da região metropolitana de São Paulo. Para tanto foi proposta uma ferramenta computacional capaz de gerar automaticamente as programações de viagens para uma linha de ônibus urbano. A programação de viagens tem um grande impacto não só na qualidade do serviço prestado aos passageiros da linha mas também no custo operacional das empresas de transporte. Portanto, o problema aqui estudado é de grande relevância prática e social. Os dados de entrada incluem uma curva com a demanda horária de passageiros da linha e um conjunto de restrições operacionais relativas à frota e aos funcionários. Na saída, deve-se produzir uma tabela com os horários das viagens além da escala de serviço completa dos carros e dos funcionários que irão operar na linha. Os algoritmos propostos por essa dissertação concentram-se no desenvolvimento de heurísticas baseadas em modelos de Programação Linear Inteira para resolver o problema de programação de viagens. Estes algoritmos foram implementados como parte de uma ferramenta computacional e os resultados são comparados com as soluções adotadas atualmente pelas empresas de transportes urbano. A análise dos resultados computacionais mostra que é possível obter reduções substanciais nos custos da operação sem que com isso haja uma redução na qualidade de serviço / Abstract: This dissertation aimed at studying and solving a real world trip planning problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of São Paulo, in Brazil. In this work we present a software that automatically generates a planning for the trips of a urban bus line. The trip planning has an enormous impact not only on the quality of the service offered to the passengers but also on the operational cost of the transportation companies. Therefore, the problem tackled here is of great importance for practical and social reasons. The input data includes the hourly demand of passengers and a set of operational constraints related to the vehicles and the employees. In the output, the trip time table as well as the vehicle and the crew schedules are produced. All the proposed algorithms in this work focus on the design of heuristics based on Integer Linear Programming models for the problem. The algorithms are implemented as part of a software whose results are compared with the solutions adopted in the bus companies nowadays. The analysis of our experiments indicates that it was possible to achieve a substantial cost reduction without loss in the quality of service / Mestrado / Mestre em Ciência da Computação

Orientadores : Christiano Lyra Filho, Fernando Jose Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-28T21:50:26Z (GMT). No. of bitstreams: 1 Vargas_PatriciaAmancio_M.pdf: 2530480 bytes, checksum: 72376c7703959b22a234b9724e9756c4 (MD5) Previous issue date: 2000 / 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-13T19:39:00Z (GMT). No. of bitstreams: 1 Takahata_AndreKazuo_M.pdf: 1113954 bytes, checksum: 18f4c96c943dced30f100b8a56c97258 (MD5) Previous issue date: 2009 / Resumo: Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. / Abstract: In this work we develop a set of generic search heuristics for solving combinatorial optimization problems formulated as linear integer programming models, using the XPRESS optimization package. This is a recent theme, in which efforts have been made in order to combine the flexibility offered by heuristics and the expressive advances achieved in the development of optimization solvers so as to obtain high quality solutions in a short time. The proposed heuristics are based on rounding solutions located on the rays of a cone whose vertex is associated with the optimal solution of the linear programming relaxation, and in feasible and infeasible trajectories relative to the frontier of such relaxation. This approach is motivated by its geometric appeal and by the success of similar approaches in heuristics for solving combinatorial problems. This work describes the development and implementation of the heuristics and presents computational tests on instances from literature. / Mestrado / Automação / Mestre em Engenharia Elétrica

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-14T08:51:37Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_M.pdf: 1632808 bytes, checksum: dfd28dc2bbd2bb5fe453a2fb1c2b7b6e (MD5) Previous issue date: 2009 / Resumo: O objetivo desta dissertação é desenvolver uma metodologia eficiente para solucionar o problema de agrupamento capacitado multicritério (PACM), no qual objetos com pesos associados são dados, os quais devem ser particionados em agrupamentos com capacidade limitada. Neste trabalho, o PACM está ambientado em um problema de reagrupamento de lotes urbanos, nos quais devem ser realizadas as leituras dos medidores de energia elétrica por concessionárias de distribuição de energia. A operação de leitura dos medidores é realizada sobre lotes geograficamente definidos e é desempenhada sobre rotas percorridas uma vez por mês pelos leituristas. A motivação deste trabalho é atribuída ao fato de que, com o passar do tempo, o tamanho e o formato dos lotes vão ficando obsoletos, devido a modificações introduzidas na conformação atual, desarranjando o equilíbrio entre os lotes e desatualizando as rotas. Por esse motivo é importante realizar um reagrupamento dos lotes buscando a diminuição dos custos operacionais de leitura, assim como a minimização dos custos e transtornos causados pelas modificações. O método proposto para resolver o problema abordado nesta dissertação é um algoritmo baseado na metaheurística GRASP (Greedy randomized adaptive search procedure). A eficiência do método proposto é testada sobre uma série de instâncias geradas e sobre uma rede real. Os experimentos computacionais demonstram a eficiência do método. / Abstract: The aim of this dissertation is to develop an eficient methodology to solve the multicriteria redistricting capacitated problem (PACM), in which objects with associated weights are given, which must be partitioned into groups with limited capacity. In this work, the PACM is inserted in to a reassignment problem of urban clusters of clients, in which the readings of the eletric energy measurement must be performed by the company of energy distribution. The reading operation is performed over lots geographically defined is performed once a month by the readers. The motivation of this work is due to the fact that the size and shape of the lots become obsolete after some time, due to modifications introduced in the current conformation, desarranging the balance between the lots and outdating the routes. For this reason it is important to achieve a reassignment of the lots trying to decrease the operational costs of reading, as well as minimizing the costs and inconvenience caused by the changes. The proposed method to solve the problem addressed in this dissertation is a algorithm based on GRASP (Greedy randomized adaptive search procedure) metaheuristic. The efectiveness of the proposed method is tested on a large number of generated instances and on a real network. Computational experiments demonstrate the efectiveness of the proposed approach. / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T05:36:32Z (GMT). No. of bitstreams: 1 Cavalcante_VictorFernandes_D.pdf: 1501954 bytes, checksum: afd9c038eef0eb384065875b1df282ca (MD5) Previous issue date: 2008 / Resumo: Uma das principais motivações para o estudo de Otimização Discreta reside no elevado número de problemas do nosso cotidiano representáveis através de modelos de Otimização Inteira e Combinatória. Em particular, muitos destes problemas podem ser formulados com Programação Inteira 0-1, o que desperta especial interesse em técnicas capazes de resolver tais modelos. Dentre as inúmeras formas de solução atualmente disponíveis para problemas desta natureza, os algoritmos baseados na técnica de relaxação Lagrangiana surgem como uma alternativa que tem tido grande sucesso na prática. Além disso, avanços consideráveis ocorreram na área de Programação Inteira com o advento da Combinatória Poliédrica, intensificando o interesse pelos algoritmos de planos de corte. Neste contexto, esta tese tem como principal objetivo verificar as potencialidades do uso combinado de Combinatória Poliédrica e relaxação Lagrangiana na resolução de dois problemas de otimização combinatória. Mais especificamente, o presente trabalho esta focado no desenvolvimento dos chamados algoritmos relax-and-cut para o problema de particionamento de conjuntos e ao problema do separador de vértices de um grafo. Sendo assim, são propostos algoritmos que combinam relaxação Lagrangiana e planos de cortes faciais para os dois problemas sob consideração. Em ambos os casos, os resultados obtidos com os testes computacionais realizados são comparados com os melhores resultados disponíveis na literatura. Os principais resultados alcançados na tese mostram que: (a) o uso combinado de relaxação Lagrangiana e planos de corte constitui uma alternativa bastante competitiva para solucionar o problema de particionamento de conjuntos, freqüentemente superando o desempenho dos melhores algoritmos disponíveis na literatura para o problema e, (b) no caso do problema do separador de vértices, além da combinação de técnicas Lagrangianas com o uso de planos de corte, a hibridização dos algoritmos relax-and-cut e branch-andcut leva á resolução de instâncias da literatura mais rapidamente que o melhor algoritmo exato conhecido para o problema até então. / Abstract: One of the main motivations for the study of Discrete Optimization resides in the huge number of problems from our daily life that can be represented through Integer and Combinatorial Optimization models. In particular, many of these problems can be cast as 0-1 Integer Programs, which gives rise to special interest on how to solve such models. Among the several ways currently available to solve problems of this nature, the algorithms based on Lagrangian relaxation techniques appears as an alternative that has had great success in practice. Besides, noticeable achievements occurred with the advent of Polyhedral Combinatorics, intensifying the interest on cutting plane algorithms. In this context, this thesis has as its main goal to verify the potentialities of the combined usage of Polyhedral Combinatorics and Lagrangian relaxation in the resolution of two combinatorial optimization problems. More specifically, the present work is focused on the development of the so-called relax-and-cut algorithms for the set partition problem and for the vertex separator problem on graphs. Therefore, algorithms combining Lagrangian relaxation and cutting planes are proposed for the two problems under consideration. In both cases, the results obtained in the computational tests carried out are compared with the best ones available in the literature. The main results achieved in the thesis show that: (a) the combined usage of Lagrangian relaxation and cutting planes constitutes a competitive alternative to solve the set partition problem, often outperforming the best algorithms available in the literature for the problem and, (b) in the case of the vertex separator problem, besides the combination of Lagrangian techniques and cutting planes, a hybridization of the relax-and-cut and branch-and-cut algorithms lead to the resolution of instances from the literature more rapidly than the best exact algorithm known for the problem so far. / Doutorado / Doutor em Ciência da Computação

Orientador : Takaaki Ohishi / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-01T18:37:40Z (GMT). No. of bitstreams: 1 Santos_ErinaldoFariasdos_M.pdf: 2058416 bytes, checksum: 0fe59960dae192acc46a52ad3dc9490d (MD5) Previous issue date: 2001 / Mestrado

Orientador : Katia Lucchesi Cavalca / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-03T13:51:06Z (GMT). No. of bitstreams: 1 Castro_HelioFioride_M.pdf: 2561520 bytes, checksum: bbc0b48e9d5c169ee070e452e68145fd (MD5) Previous issue date: 2003 / Mestrado

Orientadores: Cid Carvalho de Souza, Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T17:13:58Z (GMT). No. of bitstreams: 1 Vaz_GlauberJose_M.pdf: 2026222 bytes, checksum: 3272d1c1a8c5e8941f3b98a19e487be7 (MD5) Previous issue date: 2003 / Mestrado