[pt] Métodos que combinam estratégias normalmente encontradas em algoritmos metaeurísticos com técnicas para resolver problemas de programação inteira mista (MIP) têm apresentado ótimos resultados nos últimos anos. Este trabalho propõe dois novos algoritmos nessa linha: um algoritmo que faz pós-processamento nas soluções encontradas pelo resolvedor MIP. Os dois algoritmos utilizam um novo tipo de vizinhança, chamada de vizinhança elipsoidal, que possui fortes semelhanças com as técnicas de relinking de algoritmos PR e que neste trabalho é generalizada e extendida para múltiplas soluções. O problema generalizado de alocação (GAP) é usado para os experimentos. São testados também um resolvedor MIP puro (ILOG CPLEX versão 11) e um algoritmo branch and price que utiliza as heurísticas RINS e guided dives. Os algoritmos testados são comparados entre e com heurísticas específicas para o GAP. Os resultados são satisfatórios e indicam que as vizinhanças elipsoidais conseguem frequentemente melhorar as soluções encontradas pelo resolvedor MIP, encontrando a melhor solução para algumas instâncias. / [en] Methods that mix strategies usually found in metaheristic algorithms with techniques to solve mixed integer programming problems (MIPs) have had great results over the past few years. This wprk proposes two new algorithms in this philosophy: one is based on the Path Relink (PR) metaheuristc, while the other one is a simple algorithm that does post-processing in the solutions found by the MIP solver. Both algorithms use a new neighborhood structure, called ellipsoidal neighborhood, that has strong resemblances with the relinking step from PR algorithms and that, in this work, is generalized and extended for multiple solutions. The generalized assignment problem (GAP) is used for the computational experiments. Also tested are MIP solver (ILOG CPLEX version 11) and a branch and price algorithm that uses the RINS and guides dives heuristics. The tested algorithms are compared among themselves and with GAP-specific heuristics. The results are satisfactory and show that the ellipsoidal neighborhood can frequently improve the solutions found by the MIP solver, even finding the best result for some instances.

[pt] Compreensão de dados, codificação digital da fala, telecomunicações via celular, correção de erros de transmissão, são algumas das aplicações práticas do estudo dos códigos de cobertura, um importante ramo da área da matemática denominada teoria dos códigos. Neste trabalho são abordados dois problemas de códigos de cobertura: o problema clássico de códigos de cobertura e o recente problema denominado de códigos curtos de cobertura. Apresenta-se uma aplicação da metaeurística Busca Tabu Reativa, uma importante variação da Busca Tabu clássica, para os problemas citados. Além disto, apresenta-se uma nova técnica heurística para resolução de problemas de otimização combinatória denominada Heurística de Melhoria via Geração de Colunas (HMGC), juntamente com uma aplicação da mesma aos problemas em questão. A HMGC combina a geração atrasada de colunas, técnica usada na resolução de problemas com um grande número de variáveis de decisão (colunas), e heurísticas de busca local. É feita uma comparação dos resultados obtidos pela Busca Tabu Reativa, a Busca Tabu sem o mecanismo de reação e a HMGC, de forma a avaliar a qualidade das heurísticas apresentadas. / [en] Data compression, speech coding, móbile telecommunications and error-corretion are some of the practical apllications of the covering codes study, an important field of coding theory. This work addresses two problems of covering codes: the classic code covering problem and the recent short code covering problem. It presents an application of Reactive Tabu Search (RTS) metaheuristic for the problems cited, the RTS is an important variation of the classic Tabu Search. Moreover, it presents a new heuristic technique for solving combinatorial optimization problems named Column Generation Improbement Heuristic (CGIH). It also presents an application of CGIH for the covering codes problems. The CGIH combines the delayed column generation, technique used to solve problems with a large number of decision variables (columns), and local search heuristics. A comparison of results obtained by the Reactive Tabu Search, the Tabu Search without the reaction mechanism and the CGIH is also presented in order to assess the effectivenss of the presented heuristics.

[pt] Desde a sua origem, as abordagens a problemas de Otimização Combinatória polarizam-se entre métodos exatos e heurísticos. Recentemente, porém, estratégias que combinam ambos os métodos têm sido propostas para os mais variados problemas, apresentando resultados promissores. Nesse contexto, destacam-se os conceitos de vizinhaças de bola e elipsoidal, que realizam buscas em relação a uma ou mais soluções de referência. Este trabalho estuda a aplicação de tais vizinhanças para o Problema de Roteamento de Veículos com Restrição de Capacidade (CVRP), sobre o algoritmo de Branch-and-Cut-and-Price Robusto. Experimentos foram realizados e seus resultados analisados. / [en] Since its inception, approaches to Combinatorial Optimization were polarized between exact and heuristic methods. Recently, however, strategies that combine both methods have been proposed for various problems, showing promising results. In this context, the concepts of ball and ellipsoidal neighborhood appear, which perform a search regarding one or more reference solutions. This work studies the application of such neighborhoods for the Capacitated Vehicle Routing Problem (CVRP), using the Robust Branchand- Cut-and-Price algorithm. Experiments were made and its results were analyzed.

[pt] Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along the optical fibers as optical signals. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing these connections, so as that two lightpaths sharing a common link use different wavelengths. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a Parttion Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint susets, PCP consists in selecting and coloring only one vertex in each subset, so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computational experiments are reported comparing the new heuristics and those which already appeared in the literature.

[pt] Esta dissertação estuda modelos e algoritmos para o Problema de Alocação Generalizada (PAG) . A motivação para este estudo foi uma nova aplicação do PAG: o Problema de Carregamento de Caminhões (PCC) . A pesquisa desenvolvida concentra-se no estudo e na proposta de algoritmos aproximados (metaeurísticas) e exatos para a resolução do PAG. Os algoritmos aproximados propostos baseiam-se em um conceito recentemente criado por Fischetti e Lodi (2003), que utiliza programação matemática inteira para a exploração eficiente de vizinhanças mais abrangentes. Os resultados obtidos foram comparáveis aos melhores conhecidos, com a vantagem de exigir um esforço pequeno de implementação e um menor tempo de processamento. O algoritmo exato proposto é um algoritmo de branch-and-cut- and-price, que tem como ponto de partida o algoritmo de branch-and-price de Savelsbergh (1997). Técnicas de estabilização da geração de colunas similares às propostas por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram estudadas no âmbito desta dissertação, que experimenta com diferentes implementações deste mecanismo. O algoritmo de branch-andcut-and-price estabilizado demonstrou sua eficiência ao resolver à otimalidade instâncias que se encontravam em aberto na literatura. Finalmente, experiências com PCC permitiram que os códigos desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment Problem (PAG), models and algorithms are studied and proposed. This work was motivated by a real world application: the Truck Loading Problem (PCC). Research was done on approximated (metaheuristics) and exact algorithm for solving the PAG. The approximated algorithms proposed were based on a recent idea from Fischetti and Lodi (2003). It uses integer programming to explore wider neighborhoods. The results were compared to the best known, while demanding much less implementation effort and using less cpu time. The exact algorithm proposed is a branch-and-cut- and-price developed from the branch-and-price algorithm of Savelsbergh (1997). We used stabilized column generation techniques similar to the one by Du Merle, Villeneuve, Desrosiers and Hansen (1999), and devised experiments with different implementations of this mechanism. The resulting algorithm proved its efficiency by solving to optimality open instances from the literature. Finally, experiments with the PCC turned possible the evaluation of the codes developed on real problems.