Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-17T20:59:25Z (GMT). No. of bitstreams: 1 Azuma_ReginaMitsue_M.pdf: 2321816 bytes, checksum: 44c4417bf2a4fad2a8241c7189e4d04a (MD5) Previous issue date: 2011 / Resumo: A classe de problemas de estoque e roteamento está presente em várias áreas, incluindo indústria automobilística e gerência de numerário no reabastecimento de caixas eletrônicos. Supondo que o fornecedor é responsável pela estocagem e distribuição dos produtos, sujeito a um conjunto de restrições, o desafio que se apresenta é a determinação de uma política ótima, mais especificamente quais clientes atender, qual quantidade a ser fornecida a cada cliente e qual rota empregar visando a minimização dos custos. Este trabalho apresenta uma proposta de solução para uma das mais comuns formulações do problema: um produto é distribuído a partir de um fornecedor para vários clientes em um horizonte de tempo definido. O transporte é realizado por um veículo de capacidade limitada. Para produzir a otimização simultânea de ambos os objetivos, minimização dos custos de transporte e estoque, a proposta segue uma abordagem multiobjetivo e se baseia no uso do algoritmo SPEA2 (do inglês, Strength Pareto Evolutionary Algorithm 2), incluindo inovações na representação de soluções-candidatas, nos operadores genéticos e de busca local. A fronteira de Pareto estimada é então composta de múltiplas soluções não-dominadas, representando compromissos distintos entre custos de transporte e estoque. Como casos de estudo, são tomadas instâncias de médio porte extraídas da literatura e são geradas instâncias de grande porte. Para as instâncias de médio porte, as fronteiras de Pareto estimadas em cada caso são comparadas com as respectivas soluções ótimas da versão mono-objetivo de cada problema, pois já existe um algoritmo exato de solução para a formulação mono-objetivo de instâncias de médio porte / Abstract: The class of inventory routing problems (IRP) is present in several areas, including automotive industry and cash management for ATM networks. Given that the supplier is responsible for managing the product inventory and replenishment, subject to a set of restrictions, the challenge here is to determine an optimal policy, more specifically which retailers to serve, the quantity to deliver to each retailer and which routes to employ in order to minimize the cost. This work presents a proposal to solve one version of the IRP usually found in the scientific literature: a product is distributed from a supplier to several retailers in a defined time horizon. Shipment is performed by a vehicle with limited capacity. To perform the simultaneous optimization of both objectives, minimization of transportation and inventory costs, the proposal follows a multi-objective approach based on SPEA2 (Strength Pareto Evolutionary Algorithm 2), including innovative aspects mainly associated with the representation of candidate solutions, genetic operators and local search. The Pareto front is then composed of multiple non-dominated solutions with distinct trade-offs between transportation and inventory costs. As case studies, medium size instances extracted from the literature are considered and large size instances are generated. For the medium size instances, the estimated Pareto fronts are compared, in each case, with the corresponding optimal solutions associated with the single-objective version of each problem, given that there is already an exact algorithm to solve such medium size single-objective instances / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientadores: Christiano Lyra Filho, Celso Cavellucci / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T02:44:14Z (GMT). No. of bitstreams: 1 VizcainoGonzalez_JoseFederico_D.pdf: 9526841 bytes, checksum: 9fc3b73df592526f56693f9b329fc70c (MD5) Previous issue date: 2011 / Resumo: O trabalho desenvolve alternativas de otimização combinatória para a redução de perdas técnicas e melhoria das condições de operação de sistemas de distribuição de energia elétrica. Sua principal contribuição é na área de redução dos fluxos de reativos através da instalação e controle de bancos de capacitores. Duas alternativas de otimização são desenvolvidas. A primeira, propõe um algoritmo genético híbrido com buscas locais nas representações fenotípicas e genotípicas das soluções. A segunda alternativa utiliza conceitos de programação dinâmica no projeto de algoritmos que encontram soluções ótimas globais para o problema de localização, dimensionamento e controle de capacitores. Outro algoritmo genético híbrido, para a instalação de reguladores de tensão, complementa a possibilidade de melhoria nos perfis de tensão proporcionada pelos capacitores. Os algoritmos baseados em programação dinâmica são de complexidade polinomial; adicionalmente, suas complexidades são lineares para instâncias reais. As características desses algoritmos estabelecem novas referências para a área de localização e controle de capacitores em sistemas de distribuição de energia elétrica, hoje povoada por métodos heurísticos / Abstract: This work develops combinatorial optimization alternatives for technical loss reduction and improvements on operational conditions of power distribution networks. Its main contribution is in the area of loss reduction by decreasing reactive flows, through allocation and control of shunt capacitors banks. Two optimization strategies are proposed. The first one develops a hybrid genetic algorithm with local searches in both genotypical and fenotypical representations of solutions. The second alternative uses dynamic programming concepts in the design of algorithms that unveil global optimal solutions for capacitor location, sizing and control. Another hybrid genetic algorithm for allocation of voltage regulators complements the improvement in voltage profiles obtained with the allocation of capacitors. The algorithms based on dynamic programming concepts have polynomial-time complexity; further, they have linear-time complexity for practical applications. Therefore, these algorithms establish a new reference for the area of shunt capacitors allocation and control on power distribution systems, which is today populated by heuristic methods / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Orientadores: Carlos Alberto Favarin Murari, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-05T08:51:38Z (GMT). No. of bitstreams: 1 SilvaJunior_IreniodeJesus_D.pdf: 556445 bytes, checksum: 5c960cb84852b3168eabbeed28c1a28a (MD5) Previous issue date: 2005 / Resumo: Este trabalho apresenta algumas propostas para solucionar o problema de planejamento da expansão de sistemas de transmissão, estático e multiestágio, considerando restrições de segurança - critério de segurança (n_1), assim como para o planejamento da expansão de um sistema elétrico que satisfaça simultaneamente vários planos de programação da geração pré-especificados. Visando superar deficiências na determinação de soluções ótimas para sistemas de grande porte quando se usa métodos exatos, como decomposição de Benders e algoritmos Branch and Bound, implementouse um algoritmo genético (AG) especializado, o AG de Chu-Beasley. Utilizou-se o modelo DC para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Para a geração da população inicial e melhora de um descendente do AG de Chu-Beasley utilizou-se o algoritmo heurístico construtivo de Villasana-Garver-Salon / Abstract: This Ph.D. thesis presents some proposals to solve the transmission network expansion planning problem, static and multistage, taking into account security constraints - (n _ 1) security criterium, and the transmission expansion planning to satisfy some generation programming plans. Trying to find optimal solutions to large scale power systems, the specialized genetic algorithm of Chu-Beasley was implemented. The DC model was used to model the electrical network, and the constructive heuristic algorithm of Villasana-Garver-Salon was implemented to create the initial population and to improve the offsprings of the Chu-Beasley Genetic Algorithm / Doutorado / Energia / Doutor 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-06T02:47:37Z (GMT). No. of bitstreams: 1 Queiroz_LeonardoMendoncaOliveirade_M.pdf: 695151 bytes, checksum: 1dd5cfdea3e5f570eac87a0b801c8e25 (MD5) Previous issue date: 2005 / Resumo: Esse trabalho propõe um Algoritmo Genético Híbrido para o problema de redução de perdas em redes de distribuição de energia elétrica através de reconfigurações da rede, considerando-se as variações das demandas ao longo do dia. É adotada uma formulação que evita reconfigurações freqüentes, procurando encontrar uma única configuração para operação ao longo de todo o período em estudo, mas considerando explicitamente no processo de otimização a diversidade de variações de demanda ao longo da rede. A representação implementada garante a factibilidade dos indivíduos após a realização de cruzamento e mutação no processo de busca da melhor solução com o algoritmo genético. Foi incluída uma fase de busca local, o que caracteriza o método como um algoritmo genético híbrido. Com o objetivo de alternar entre estratégias de intensificação e diversificação, foram utilizadas técnicas de adaptação de parâmetros; mais especificamente, da probabilidade de mutação. Estudos com redes reais de médio e grande porte ilustram a aplicabilidade da metodologia proposta e sugerem alternativas para desdobramentos do trabalho / Abstract: This work proposes a Hybrid Genetic Algorithm approach to the problem of loss reduction in distribution systems by network reconfiguration strategies, under variable demands. A formulation that avoids frequent reconfigurations is adopted, searching for a fixed configuration to operate for the whole planning period, but taking into account demand variations on the optimization processo The chromosome representation adopted in the algorithm guarantees the factibility of the individuaIs after crossover and mutation operations on the process of searching for the best solution. A local search procedure is included, characterizing an hybrid implementation. Techniques of adaption of parameters were used (specifically mutation probability), to provide alternation between intensification and diversification strategies. Case studies with real distribution networks provide information on the possibilities of the approach and suggest alternatives to further investigations / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T15:19:37Z (GMT). No. of bitstreams: 1 Pereira_RomuloAlbuquerque_M.pdf: 1452483 bytes, checksum: 19f11b532a512f1e86efa79195a4e8ce (MD5) Previous issue date: 2005 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento das atividades de desenvolvimento de poços de petróleo em alto mar. Uma versão mais simples deste mesmo problema foi provada ser NP- difícil. Nosso estudo se concentrou no problema real enfrentado pela Petrobrás, com todas suas características e nuances. Antes que locais promissores de bacias petrolíferas sejam efetivamente desenvolvidos em poços de petróleo produtivos, é necessário realizar diversas atividades de perfuração, completarão e interligação nesses locais. O escalonamento dessas atividades deve satisfazer várias restrições conflitantes e buscar a maximização da produção de petróleo em um dado horizonte de tempo. O problema foi atacado em duas etapas: uma sem considerar o deslocamento de recursos e outra considerando-os. Para tal, adotamos a estratégia Greedy Randomized Adaptive Search Procedure (GRASP) e incorporamos várias técnicas específicas para obter melhor desempenho e qualidade da solução final. Os resultados são comparados com outros produzidos por uma ferramenta computacional baseada em Programação por Restrições (PR). Esta última, já em uso e bem aceita na empresa, foi desenvolvida pela Petrobrás. Resultados comparativos realizados em instâncias reais indicam que a implementação GRASP supera a ferramenta de PR produzindo soluções com expressivos aumentos de produção / Abstract: This dissertation aimed at studying and solving a real world scheduling problem. We deal with the scheduling of offshore oil well development activities. A simpler version of this same problem was proved to be in NP-hard. Our approach treats this problem as faced by Petrobras, with all its characteristics and details. Before promising locations at petroliferous basins become productive oil wells, it is often necessary to complete activities of drilling, completion and interconnection at these locations. The scheduling of such activities must satisfy several conflicting constraints and aim at the maximization of oil production. The problem was solved in two parts: one without considering resource displacements and other taking into account such displacements. For such, we used a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and used several techniques and variants in order to obtain more efficiency and produce better solutions. The results are compared with schedules produced by a well-accepted constraint programming implementation. Computational experience on real instances indicates that the GRASP implementation is competitive, outperforming the constraint programming implementation / Mestrado / Otimização Combinatoria / Mestre em Ciência da Computação

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-08T10:15:19Z (GMT). No. of bitstreams: 1 Araujo_OlintoCesarBasside_D.pdf: 1592360 bytes, checksum: 71dd5f2565cd93013aa027127157c442 (MD5) Previous issue date: 2006 / Resumo: A adoção de contêineres em grande escala tornou possível o desenvolvimento do transporte multimodal. Atualmente, carregamento de caixas em contêineres é uma importante atividade em empresas que têm no transporte de carga um fator logístico de alto custo. Este trabalho apresenta o desenvolvimento e aplicação de metaheurísticas com memória adaptativa para a resolução de problemas de corte e empacotamento tridimensional, bem como a integração destes com o problema de roteamento de veículos. Mais especificamente, são tratados os problemas de carregamento de contêiner, bin packing tridimensional e roteamento de veículos capacitados com restrições de empacotamento tridimensional. Uma nova abordagem, baseada em cubóides de tamanho variável, é utilizada para calcular os padrões de carregamento tridimensional em todos os métodos propostos. Restrições de orientação, estabilidade, centro de gravidade, projeção da base de apoio e múltiplos destinos são consideradas. Extensivos testes computacionais são realizados para demonstrar o desempenho das abordagenspropostas / Abstract: The wide-scale adoption of the containers made the development of the multimodal transport possible. Nowadays, shipment of boxes in containers is an important activity for companies that have in the load transport a logistic factor of high cost. This work presents the development and the application of metaheuristics with adaptive memory in order to solve three-dimensional cutting and packing problems, as well as their integration with the vehicle routing problem. In particular, problems of container loading, three-dimensional bin packing and vehicle routing with three-dimensional packing constraints are considered. Furthermore, a new approach based on maximal cuboids that fit in given empty spaces is used to calculate the packing patterns in the proposed methods. Constrains on orientation, stability, center of gravity, overhang and multiple destination are considered. Extensive computational experiments are carried out to demonstrate the performance of the proposed approaches / Doutorado / Automação / Doutor 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-09T05:57:31Z (GMT). No. of bitstreams: 1 Usberti_FabioLuiz_M.pdf: 37565259 bytes, checksum: cddb8b852bd82318a8c784f1f223a076 (MD5) Previous issue date: 2007 / Resumo: Esse trabalho se dedicou ao estudo dos algoritmos para roteamento de leituristas, incluindo propostas de alteração que resultem na melhoria da qualidade dos resultados. A motivação é proveniente da alta demanda por soluções computacionais para esse problema, ainda pouco estudado devido às peculiaridades que lhe são inerentes. Encontram-se na literatura duas heurísticas, de estratégias distintas e antagônicas para esse problema. Uma das heurísticas procura construir a rota ignorando a restrição de capacidade, para posterior particionamento dessa rota em subrotas, cada qual destinada a um leiturista (¿route first, cluster second¿). A outra heurística, em uma abordagem inversa, primeiramente subdivide a região de trabalho dos leituristas, para posterior roteamento dessas partições (¿cluster first, route second¿). Essas duas heurísticas foram testadas exaustivamente, tornando possível localizar aspectos sujeitos à melhoria, dando origem a duas novas heurísticas. Foi gerada uma base de testes contendo 144 instâncias que simulam as condições reais de trabalho dos leituristas, classificadas de acordo com o tamanho e dificuldade. A partir das soluções provenientes dos quatro algoritmos foi possível analisá-los comparativamente, avaliando o melhor em um âmbito geral (envolvendo todos os algoritmos) e específico (algoritmos de mesmo tipo, ¿route first cluster second¿ ou ¿cluster first route second¿), segundo critérios de qualidade pré-definidos: número de rotas, tempo de percurso, violação da carga horária e tempo computacional. Os resultados revelam que os novos algoritmos foram melhores tanto na comparação específica quanto na comparação geral / Abstract: This work¿s main study object consists on algorithms for routing meter readers, from which proposals towards solution¿s improvement are made. The demand for computational results concerning this problem, added to literature little attention due to its inherited peculiarities, has been the outmost motivation. Two preexisting heuristics from literature, with distinct and antagonic strategies, are pointed out. One of these heuristics atempt to create a single route, dismissing the capacity restriction, and then partitionates this route into subroutes, each of them destinated to one meter reader (route first, cluster second). The other heuristic, in an inverse approach, first splits the meter reader¿s working area, and only then routes each of these partitions (cluster first, route second). The two heuristics were tested to exaustion, allowing enumeration of weak aspects subject to improvement. Therefore, two new heuristics were developed, based upon the originals, however adapted in order to outperform solution¿s quality. A testing base containing 144 instances was generated, simulating meter readers realistic labor¿s conditions, classified by size and difficulty. Through solutions provided by the four algorithms, comparison analyses have taken place, evaluating in a general (involving all algorithms) and specific manner (same kind algorithms, i.e., route first, cluster second or cluster first, route second), considering four predefined quality criteria: number of routes, deadheading time, violation of shiftwork time and computational time. Results revealed that the new algorithms achieved better solutions on specific and general comparisons / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores: Paulo Morelato França, Vinicius Jacques Garcia / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:49:29Z (GMT). No. of bitstreams: 1 Magalhaes_AlanadaSilva_M.pdf: 1141597 bytes, checksum: 29180007fa94c919a3260202a743d587 (MD5) Previous issue date: 2007 / Resumo: Sistemas de distribuição de energia elétrica podem ser reconfigurados em sua topologia visando operações de manutenção, reenergização de áreas escuras causadas por temporais ou balanceamento da carga dos alimentadores. Este trabalho considera o problema de reconfiguração da rede com o objetivo de balancear a carga dos alimentadores sem deixar de observar as restrições de capacidade dos alimentadores, de queda de tensão nas barras de carga e de radialidade da rede. Considera-se também um caso particular no qual há a necessidade de transferir carga de um determinado alimentador para os seus adjacentes por questões operativas, a fim de facilitar uma eventual manutenção ou visando a restauração de áreas desenergizadas. Depois da definição matemática do problema e da revisão da literatura especializada, são descritos sete algoritmos baseados em um método de balanceamento de carga conhecido como ¿Distance Measurement Technique (DMT)¿ aplicado a várias técnicas, inclusive a técnica de multichaveamento, usadas para determinar as operações de chaveamento envolvidas. Por fim, por meio de estudos com redes reais de médio e grande porte avalia-se a aplicabilidade das abordagens propostas / Abstract: Electric energy distribution systems can be reconfigurated aiming at maintenance operations, reenergizing dark areas caused by storms or feeder load balancing.This work considers the network reconfiguration problem with the load balancing objective while respecting constraints like feeder and voltage limits as well as the maintenance of a radial structure. It is also considered the particular case in which one wants to transfer load from a given feeder to its adjacent ones caused by maintenance operations or service restoration. After defining the mathematical formulation proposed and presenting the bibliographical survey, seven algorithms are presented based on a method for load balancing known as Distance Measurement Technique (DMT) applied to several technique, also the multitier technique, used to determine the switching operations involved. Finally, the effectiveness of these proposed methods are proved in a set of four systems, two of them referring to real Brazilian systems / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores: Fernando Jose Von Zuben, Leandro Nunes de Castro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T19:14:33Z (GMT). No. of bitstreams: 1 Franca_FabricioOlivettide_M.pdf: 2824607 bytes, checksum: 3de6277fbb2c8c3460d62b4d81d14f73 (MD5) Previous issue date: 2005 / Resumo: Esta dissertação propõe algoritmos bio-inspirados para a solução de problemas de otimização dinâmica, ou seja, problemas em que a superfície de otimização no espaço de busca sofre variações diversas ao longo do tempo. Com a variação, no tempo, de número, posição e qualidade dos ótimos locais, as técnicas de programação matemática tendem a apresentar uma acentuada degradação de desempenho, pois geralmente foram concebidas para tratar do caso estático. Algoritmos populacionais, controle dinâmico do número de indivíduos na população, estratégias de busca local e uso eficaz de memória são requisitos desejados para o sucesso da otimização dinâmica, sendo contemplados nas propostas de solução implementadas nesta dissertação. Os algoritmos a serem apresentados e comparados com alternativas competitivas presentes na literatura são baseados em funcionalidades e estruturas de processamento de sistemas imunológicos e de colônias de formigas. Pelo fato de considerarem todos os requisitos para uma busca eficaz em ambientes dinâmicos, o desempenho dos algoritmos imuno-inspirados se mostrou superior em todos os critérios considerados para comparação dos resultados dos experimentos. / Abstract: This dissertation proposes bio-inspired algorithms to solve dynamic optimization problems, i.e., problems for which the optimization surface on the search space suffers several changes over time. With such variation of number, position and quality of local optima, mathematical programming techniques may present degradation of performance, because they were usually conceived to deal with static problems. Population-based algorithms, dynamic control of the population size, local search strategies and an efficient memory usage are desirable requirements to a proper treatment of dynamic optimization problems, thus being incorporated into the solution strategies implemented here. The algorithms to be presented, and compared with competitive alternatives available in the literature, are based on functionalities and processing structures of immune systems and ant colonies. Due to the capability of incorporating all the requirements for an efficient search on dynamic environments, the immune-inspired approaches overcome the others in all the performance criteria adopted to evaluate the experimental results. / Mestrado / Engenharia de Computaçã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-15T11:41:44Z (GMT). No. of bitstreams: 1 Hoshino_EdnaAyako_D.pdf: 1434503 bytes, checksum: c1b32d8a6dc810d6d7ff6100d1a77c79 (MD5) Previous issue date: 2009 / Resumo: Nesta tese,dois problemas de otimização combinatória em grafos são modelados por programação linear inteira e resolvidos através de técnicas de geração de colunas. Os dois casos correspondem a generalizações de problemas clássicos em grafos e que ocorrem em muitas situações práticas. O primeiro, chamado problema dos anéis-estrelas capacitados, é uma generalização do problema de roteamento de veículos e modela situações reais encontradas nas áreas de logística de distribuição e de transporte. O segundo, conhecido por problema da coloração particionada, generaliza o problema da coloração de vértices em grafos e ocorre em aplicações no projeto de redes ópticas. As formulações de programação linear inteira desenvolvidas neste trabalho para modelar ambos os problemas estão relacionadas 'a técnica da decomposição de Dantzig-Wolfe e usam uma quantidade exponencialmente grande de variáveis de decisão . Nestas formulações, cada uma das variáveis representa uma estrutura específica do problema sendo estudado. No problema dos anéis-estrelas capacitados, cada variável está associada a um anel-estrela e, no problema da coloração particionada, a um conjunto independente. As relaxações lineares destes tipos de modelos, em geral, apresentam limitantes duais mais apertados que outros modelos compactos, isto é, definidos para um número polinomial de variáveis. Nesta tese, nós avaliamos estas novas formulações, comparando-as com outros modelos conhecidos para os problemas estudados. Além disso, nos dois casos, projetamos e implementamos algoritmos exatos do tipo branch-and-price e/ou branch-and-cut-and-price capazes de computar os modelos propostos. Experimentos computacionais foram realizados com estes algoritmos que confirmaram a adequação das técnicas aqui empregadas. Tanto para o problema dos anéis-estrelas capacitados quanto para o problema da coloração particionada, os resultados alcançados por nós foram comparados com aqueles reportados na literatura e mostraram que os algoritmos baseados em geração de colunas tiveram desempenho melhor que os algoritmos propostos anteriormente / Abstract: In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação