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: Andreia Cristina Ribeiro / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-11T11:28:46Z (GMT). No. of bitstreams: 1 Assis_LucianaMafaldaEliasde_M.pdf: 10126493 bytes, checksum: bb2628e76f90df6deb24a9011e535714 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho são apresentados vários resultados importantes da Análise Combinatória com destaque para o Princípio da Inclusão e Exclusão. Relevantes aplicações deste princípio são abordadas / Abstract: In this work we present important results from enumerative combinatorics, with an emphasis on the Principle of Inclusion and Exclusion. Relevant applications of this principle are presented to illustrate its use / Mestrado / Mestre em Matemática

Esta dissertação descreve um jogo de baralho com caráter pedagógico, Resto Zero, o qual apresenta forte ligação com probabilidade, divisibilidade, análise combinatória e operações aritméticas elementares. Especificamente calculamos a probabilidade de alguns eventos principais que ocorrem no desenvolvimento do jogo. Apresentamos também uma relação do uso do Resto Zero aos anos/séries em que pode ser trabalhado. / In this dissertation we present and develop a simple game based upon a deck of cards which we call Residue Zero. We study and describe some characteristics of this game by observing its strong connections with probability, combinatorics and basic arithmetic operations. In particular, we compute the probability of several events that occur during the development of this game. We finally provide a relation of the scholar grades in which some features of this game could be worked out.

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

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T17:43:38Z (GMT). No. of bitstreams: 1 Mendes_AlexandredeSousa_D.pdf: 1237414 bytes, checksum: 79ab61ac72d53bfe2374807e58a1f03c (MD5) Previous issue date: 2003 / Doutorado

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T17:30:49Z (GMT). No. of bitstreams: 1 Yamashita_DeniseSato_D.pdf: 2970003 bytes, checksum: 72c1667962da475bb3a8d324efecf62b (MD5) Previous issue date: 2003 / Doutorado