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-25T19:21:35Z (GMT). No. of bitstreams: 1 Cavellucci_Celso_D.pdf: 7349643 bytes, checksum: 36de213206369c56664ecd7794007a00 (MD5) Previous issue date: 1998 / Resumo: Este trabalho apresenta uma nova abordagem para a minimização das perdas em sistemas de distribuição de energia elétrica.A minimização das perdas é obtida por meio da reconfiguração das redes de distribuição.Considerando que essas redes operam com uma configuração radial, busca-se a árvore recobridora do grafo que representa a rede de distribuição, que minimize as perdas de energia e satisfaça as restrições de demanda e os limites do fluxo de corrente nas linhas; em outras palavras, trata-se de uma generalização do problema da árvore recobridora de custo mínimo. A generalização é devida às variações nos custos dos arcos com a mudança da configuração.A solução ótima global desse problema combinatório é obtida por um procedimento recursivo em duas fases, onde se combina as técnicas de fluxo não lineares e estratégias de busca usadas na área de inteligência artificial. Na primeira etapa a restrição de operação radial da rede é relaxada, levando a uma solução otimista para o problema; as informações desta solução são usadas na segunda etapa, onde busca-se a solução factível de custo mínimo. As etapas são repetidas, até que a configuração de rede radial de mínimas perdas seja encontrada. O procedimento recursivo é controlado por estratégias de busca inteligentes para contornar a explosão exponencial do esforço computacional. Três procedimentos de busca informada foram concebidos para obter uma árvore recobridora de perdas mínimas: backtracking infonnado, bactracking heurístico e algoritmo A*. Apresenta-se também procedimentos de paralelização dos algoritmos. Estudos de caso são discutidos, indicando as possibilidades e limitações da abordagem proposta / Abstract: This thesis presents a new approach to minimize losses in e1ectricalenergy distribution systems. The loss minimization is accomplished with the reconfiguration of the distribution network. Since distribution networks must operate radially, the problem can be regarded as a generalization of the minimum spanning tree problem. It seeks a spanning tree for a graph that represents the distribution network which minimizes losses while meetting loadsand satisfying constraints on line flow capacities - the generalization is due to variation in the costs as the network configuration changes. A global optimum to this combinatorial prob1em is found through a recursive two-step procedure, merging non-1inear network flow techniques with intelligent search strategies. Radial operation is relaxed in a first step, leading to an optimistic solution; information from the oprimist solution are used to approach feasibility in the second step. Both steps are repeated, driven by intelligent search techniques to cope with computational intractability. Three informed search procedures were conceived to obtain a minimum-loss spanning tree: enhanced backtracking, heuristic backtracking and A* algorithm. Parallel implementations of the algorithms are also presented. Case studies are discussed, providing guidelines about the possibilities and limitations of the proposed approach / Doutorado / Doutor em Engenharia Elétrica

Orientadores: Christiano Lyra Filho, Marcos Carneiro da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T23:00:34Z (GMT). No. of bitstreams: 1 Pinheiro_DanielBachega_M.pdf: 8970194 bytes, checksum: 94df48a445de9dd6f74c3350a54bc70b (MD5) Previous issue date: 1999 / Resumo: Esta tese apresenta o desenvolvimento de uma metodologia e um programa computacional para o projeto de rede externa de telefonia. Busca-se a minimização de custos através de métodos formais de otimização e automatiza-se o processo de projeto, levando a melhores tomadas de decisões. A metodologia foi desenvolvida para um cenário onde se deseja capacitar as redes atuais para atender as demandas reprimidas. As rede externas telefônicas ligam o assinante ao centro de fios através de duas sub-redes, a rede primária e a rede secundária. O projeto de um conjunto dessas redes é um problema combinatorial complexo e de difícil tratamento; a metodologia apresentada divide-se em três etapas, utilizando técnicas formais de otimização combinatória em conjunto com heurísticas construtivas e de melhoria. Inicialmente, localizam-se os armários telefônicos, que são pontos de "passagem" da rede primária para a rede secundária. Em seguida, minimiza-se a utilização de cabos e a construção de novos dutos e galerias na rede primária, avaliando-se, inclusive, alternativas de utilização de novas tecnologias, como as fibras e armários óticos. Finalmente, procura-se minimizar a instalação de novos cabos na rede secundária. Para ambas as sub-redes, aproveitam-se as facilidades presentes nas redes telefônicas existentes. Estudos de casos detalhados ilustram a aplicação da metodologia / Abstract: This thesis presents the development of a methodology and software for telecommunications access network design. It adopts a network flow optimizations methods and heuristics to minimize costs, leading to better decisions. The methodology was developed for a scenario where the network should be improved to deal with future demands. The access network connects the switching center to the subscribers, through the primary and secondary networks. Defining the best alternatives for both networks is a complex combinatorial problem; the methodology is divided in three stages that uses formal combinatorial optimization techniques in conjunction with a set of constructive heuristics and local search. Initially, equipments that connect primary and secondary networks are located. Following, the combined costs of cables and galleries is minimi zed for the primary network; the optimization includes the evaluation of using new technologies, such as fiber and optics equipment. Finally, the use of new cables in the secondary network is minimized. All the installed facilities are taken in account for both networks (primary and secondary). Detailed case studies illustrate application of the methodology / Mestrado / Mestre em Engenharia Elétrica

Tese (livre-docencia) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-15T01:13:46Z (GMT). No. of bitstreams: 1 PalazzoJunior_Reginaldo_LD.pdf: 6624330 bytes, checksum: 122b08f938ace4c9e54a3b41dbb9edff (MD5) Previous issue date: 1987 / Resumo: Neste trabalho procuramos estabelecer os conceitos e métodos utilizados no desenvolvimento das pesquisas sobre códigos de treliça dando um novo enfoque aos problemas: a) de determinação dos códigos ótimos invariantes no tempo sobre o corpo de Galois com q elementos, sob o critério de mínima Pb através da equivalência com o problema de otimização combina-torial; b) de determinação dos códigos ótimos variantes no tempo, sob o critério minimização da função enumeradora; c) equivalência do problema tratado em a) com aplicações em crip tografia; d) determinação da função enumeradora (generalizada) para códigos de treliça não lineares com aplicações em Múltiplo Acesso, Modulação por Sobreposição, Resposta Parcial, Modulação por Codificação de Treliça e etc... / Abstract: Not informed / Tese (livre-docencia) - Univer / Teoria de Informação e Codificação / Livre-Docente em Engenharia Eletrica

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

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-04T14:30:07Z (GMT). No. of bitstreams: 1 Mortati_CamilaFrederico_M.pdf: 341927 bytes, checksum: 5b1a9d9a8e6c0852c0e86425852e2584 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui proposto / Abstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work / Mestrado / Automação / Mestre em Engenharia Elétrica

Made available in DSpace on 2014-06-12T23:14:02Z (GMT). No. of bitstreams: 2 arquivo4311_1.pdf: 1045018 bytes, checksum: 1cb0d43dc431f5fb1dc2d8e2d09d883e (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A absorção de dois fótons por moléculas orgânicas possui muitas aplicações tecnológicas importantes, fazendo a modelagem teórica e a síntese de novas moléculas com valores elevados de seção de choque para absorção de dois fótons, δ (ω ) , atividades muito necessárias. A absorção de dois fótons é um processo óptico não-linear proporcional à parte imaginária da segunda hiperpolarizabilidade dinâmica da molécula, Imγ (−ω;ω,ω,−ω ) . Nos nossos cálculos de δ (ω ) empregamos uma versão truncada, TP ijkl γ , da componente da hiperpolarizabilidade que contribui para absorção de dois fótons, juntamente com uma expressão simplificada, porém exata, para a componente negativa da hiperpolarizabilidade, N ijkl γ . Através de simulações numéricas, demonstra-se que esta equação truncada produz resultados de δ (ω ) que são praticamente iguais aos obtidos utilizando-se a equação não-truncada longe da condição de dupla ressonância. Também são descritas algumas propriedades desta equação de soma sobre estados. Motivados pela proposta recente de que a inclusão de defeitos carregados positivamente na estrutura de uma molécula aumenta o valor máximo da sua seção de choque para absorção de dois fótons, max. δ , decidimos explorar a separação de cargas intrínseca dos anéis mesoiônicos do tipo A para realizar um estudo de modelagem molecular combinatória de novos sistemas com valores elevados de max. δ . Os anéis mesoiônicos são betaínas mesoméricas heterocíclicas conjugadas isoconjugadas a diânions de hidrocarbonetos pares não-alternantes. Para obter os valores das energias e dipolos de transição, necessários para o cálculo de max. δ , foram realizados cálculos de interação de configuração (CI)com o Hamiltoniano semi-empírico INDO/S. Antes dos cálculos CI as geometrias das moléculas são otimizadas com o método semi-empírico AM1. O procedimento computacional é validado e mostra-se que, incluindo apenas excitações simples no CI, somos capazes de obter valores, dos comprimentos de onda de absorção de um e dois fótons e da seção de choque para absorção de dois fótons, apropriados para a realização de estudos de modelagem molecular de sistemas para aplicações envolvendo a absorção de dois fótons. Nos estudos combinatórios são analisados compostos orgânicos contendo tanto arranjos dipolares quanto quadrupolares de anéis mesoiônicos. É mostrado que os arranjos dipolares não apresentam valores de max. δ muito elevados. Para os compostos contendo arranjos quadrupolares de dois anéis mesoiônicos, é mostrado que os valores mais elevados de max. δ são obtidos para sistemas nos quais estes anéis estão ligados pela suas regiões catiônicas à ponte poliênica. Também é mostrado que, no caso destes arranjos quadrupolares, os maiores valores de max. δ não são necessariamente obtidos para as pontes poliênicas mais longas. É mostrado que, no caso de compostos contendo anéis mesoiônicos, é importante prestar-se atenção à distância entre os picos de absorção de um e dois fótons na hora de escolher os compostos mais promissores para síntese. Neste trabalho é mostrado que compostos orgânicos incorporando anéis mesoiônicos são bons candidatos para sistemas com grandes seções de choque para absorção de dois fótons

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-02T15:07:51Z No. of bitstreams: 1 texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5) / Made available in DSpace on 2017-02-02T15:07:51Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5) Previous issue date: 2016-07-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas pa- ralelas não-relacionadas em que as tarefas causam desgastes nas máquinas. Este fator diminui o desempenho das máquinas levando ao aumento do tempo de pro- cessamento das tarefas ao longo do tempo. O objetivo do problema é encontrar as sequências de processamento de tarefas em cada máquina de tal maneira que os desgastes das máquinas sejam reduzidos e, consequentemente, minimizar o tempo máximo de conclusão de todas as tarefas, conhecido como makespan. Neste traba- lho, inicialmente, é proposto um novo modelo de Programação Inteira Mista baseado na geração de padrões (conjuntos de tarefas) para cada máquina, com objetivo de obter soluções ótimas para o problema. Dado que o problema é NP-Difícil para mais de uma máquina, dois algoritmos heurísticos são propostos para obter solu- ções de alta qualidade em baixo tempo computacional. Os algoritmos são baseados nas meta-heurísticas Iterated Local Search (ILS) e Iterated Greedy (IG), respecti- vamente. Também, as heurísticas ILS e IG são combinadas com uma variante do método Variable Neighborhood Descent (VND), que utiliza uma ordenação aleatória das vizinhanças (RVND) na fase da busca local, obtendo dois algoritmos híbridos denominados ILS-RVND e IG-RVND. O benchmark usado nos experimentos compu- tacionais usa 900 instâncias de médio porte disponíveis na literatura, e 900 instâncias de grande porte geradas neste trabalho. Os algoritmos são comparados entre si e também com um algoritmo Simulated Annealing (SA) proposto na literatura para o mesmo problema. Os testes realizados mostram que os desempenhos dos algoritmos propostos são significativamente superiores em relação ao algoritmo SA. / This work addresses an unrelated parallel machine scheduling problem in which the jobs cause deterioration of the machines. This factor decreases the performance of the machines, causing an increasing of the jobs over time. The problem is to find the processing sequence of jobs on each machine in order to reduce the deterioration of the machines and consequently minimize the maximum completion time of jobs (makespan). In this work, initially, we propose a new Mixed-Integer Programming model based on patterns (sets of jobs) generation to find optimal solution of the pro- blem. Since the problem is NP-hard when the number of machines is greater than one, two heuristic algorithms are proposed to obtain near-optimal solutions in reaso- nable computational time. The algorithms are based on the meta-heuristics Iterated Local Search (ILS) and Iterated Greedy (IG), respectively. Also, the algorithms ILS and IG are coupled with a variant of the Variable Neighborhood Descent (VND) method that uses a random ordering of neighborhoods (RVND) in local search phase, obtaining two hybrid algorithms called ILS-RVND and IG-RVND. The benchmark used in computational experiments uses 900 medium-size instances available in the literature, and 900 large-size instances generated in this work. The algorithms are compared against each other and are also compared with a Simulated Annealing (SA) algorithm proposed in the literature for the problem under study. The tests show that the proposed algorithms have superior performances compared to the SA algorithm.

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade. / Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality. / Doutorado / Doutor em Ciência da Computação

Orientador: Walter Alexandre Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-20T18:42:45Z (GMT). No. of bitstreams: 1 MonteCarmelo_EmersonLuizdo_M.pdf: 2409540 bytes, checksum: b6122d0996eacaf5c5bc2ab13ba69bd3 (MD5) Previous issue date: 1995 / Resumo: Não informado / Abstracdt: Not informed / Mestrado / Mestre em Matemática

Submitted by Alexandra Feitosa (alexandra.feitosa@ufpe.br) on 2017-07-25T13:27:14Z No. of bitstreams: 1 2012-Dissertacao-JorgeCasierra.pdf: 2433959 bytes, checksum: b9ef1bdd09d186c57d8e2863777c8f98 (MD5) / Made available in DSpace on 2017-07-25T13:27:14Z (GMT). No. of bitstreams: 1 2012-Dissertacao-JorgeCasierra.pdf: 2433959 bytes, checksum: b9ef1bdd09d186c57d8e2863777c8f98 (MD5) Previous issue date: 2012-07-31 / Apresentamos uma solução alternativa para a cadeia de Isingna presença de campo comcondições de contorno aberta e periódica, nos ensembles microcanônico e canônico, a partirde uma perspectiva combinatória e topológica unificada. Em particular, o cálculo da entropiacomo função da energia revela um valor residual para campos críticos, um fenômeno para oqual fornecemos uma interpretação topológica e uma conexãocom a sequência de Fibonacci. Afunção de partição canônica é identificada como a função geradora combinatorial do problemamicrocanônico. Uma análise detalhada da termodinâmica comvariação do campo magnético,incluindo temperaturas positivas e negativas, revela características interessantes. Por fim, nósenfatizamos que nossa abordagem combinatória para o ensemble canônico é útil no cálculo ex-ato do valor médio da característica de Euler associada com as configurações de spin da cadeia,a qual é descontínua nos referidos campos críticos, e cujo comportamento com a temperaturaé esperado estar associado com o comportamento crítico da cadeia. De fato, nossos resultadosmostram que uma conjectura proposta também é válida para a cadeia de Ising:χ(TC) =0, ondeTC=0 é a temperatura crítica. / We present an alternative solution of the Ising chain in a field under free and periodic bound-ary conditions, in the microcanonical and canonical ensembles, from a unified combinatorialand topological perspective. In particular, the computation of the entropy as a function of theenergy unveils a residual value for critical fields, a phenomenon for which we provide a topo-logical interpretation and a connection with the Fibonaccisequence. The canonical partitionfunction is identified as the combinatorial generating function of the microcanonical problem.A detailed analysis of the thermodynamics with varying magnetic field, including positive andnegative temperatures, reveals interesting features. Last, we emphasize that our combinatorialapproach to the canonical ensemble is suitable for the exactcomputation of the thermal averagevalue of the Euler Characteristic associated with the spin configurations of the chain, which isdiscontinuous at the referred critical fields, and whose temperature behavior is expected to de-termine the phase transition of the model. Indeed, our results show that the conjecture is validfor the Ising chain:χ(TC) =0, whereTC=0 is the critical temperature.