[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.

[pt] Os problemas de roteamento estão entre os problemas combinatórios mais difíceis de encontrar limites melhores do que os existentes ou de provar novas soluções ótimas. Nesta tese, são abordados o Capacitated Arc Routing Problem (CARP) e o Generalized Vehicle Routing Problem (GVRP). Em ambos os problemas, existe um conjunto de clientes os quais estão espalhados por um grafo dado, onde cada cliente possui uma demanda que deve ser atendida por exatamente um veículo de um conjunto de veículos idênticos. Os custos de travessia e o vértice de depósito são dados. O objetivo é encontrar rotas que coletam todas as demandas com custo mínimo, sem exceder a capacidade de nenhum veículo. No CARP, os clientes são um subconjunto de arestas, chamadas de arestas requireds, e para o GVRP, cada cliente é um subconjunto de vértices, chamado de grupo, onde cada grupo deve ser atendido visitando-se exatamente um vértice deste grupo. Além disto, vale notar que quando cada grupo possui apenas um vértice, o problema passa a ser o Capacitated Vehicle Routing Problem (CVRP). Primeiramente, são investigados métodos para melhorar os limites inferiores de instâncias de grande porte. É proposta a exploração da velocidade de uma heurística dual ascent para gerar cortes de capacidade. Em seguida, é apresentado um algoritmo de geração de colunas com um pricing eficiente para um tipo especial de rota não-elementar. O pricing proposto combina a técnica Decremental State-Space Relaxation (DSSR) com limites de complemento. Estas técnicas permitem o fortalecimento da regra de dominância entre as rotas, reduzindo drasticamente o número total de rótulos utilizados pela programação dinâmica. Finalmente, um algoritmo de branch-cut-and-price é criado o qual usa a geração de colunas e a separação de cortes previamente apresentadas. Além disto, este branch-cut-and-price é implementado usando strong branching e fixação por custo reduzido. Ao fim de cada parte, são apresentados resultados computacionais os quais avaliam a qualidade dos algoritmos propostos, os quais obtém novos limites inferiores para um grande número de instâncias do CARP e do GVRP. / [en] Routing problems stand among the hardest combinatorial problems to find high quality bounds or to prove new optimal solutions. In this thesis, we tackle the Capacitated Arc Routing Problem (CARP) and the Generalized Vehicle Routing Problem (GVRP). For both problems, there are a set of customers spread over a given graph, where each customer has a demand which must be serviced by exactly one vehicle from a set of identical vehicles. The traversal costs and a depot vertex are given. The objective is to find routes that collect all the demands, without exceeding the capacity of any vehicle, at minimum cost. For the CARP, the customers are a subset of edges, called the required edges, and for the GVRP, each customer is a subset of vertices, called clusters, where each cluster must be serviced by visiting exactly one vertex of it. Furthermore, it is noteworthy that when every cluster contains just a single vertex, the problem is the Capacitated Vehicle Routing Problem (CVRP). Firstly, we investigate methods to improve lower bounds for large scale instances. We propose to explore the speed of a new dual ascent heuristic to generate capacity cuts. The quality of the cuts found is next improved with a new exact separation which is used in the linear program resolution that follows the dual heuristic. Following, we present a column generation algorithm with an efficient pricing for a special kind of non-elementary routes. The proposed pricing algorithm combines Decremental State-Space Relaxation(DSSR) technique with completion bounds. These techniques allow the strengthening of the domination rule between routes, drastically reducing the total number of labels used during the dynamic programming. Finally, we devise a branch-cut-and-price algorithm which uses the previously presented column generation and cut separation. Moreover, this branch-cutand- price is implemented using strong branching and reduced cost fixing. At the end of each part, we present computational experiments which evaluate the quality of the proposed algorithms and show new best lower bounds for a large number of CARP and GVRP instances.

[pt] Ao longo dos últimos anos o desenvolvimento da Pesquisa Operacional foi fundamental para o crescimento da indústria aérea. No Brasil, o órgão responsável pela fiscalização da aviação civil é a Agência Nacional de Aviação Civil (ANAC). O objetivo da dissertação é desenvolver um modelo de otimização para localização-alocação de pessoal (servidores) e aplicá-lo à um estudo de caso da ANAC, no contexto de Safety Oversight. Uma revisão sistematizada de literatura foi conduzida para identificar os gaps e soluções recentes na literatura de problemas de facility location. O objetivo descrito foi alcançado e o modelo matemático foi validado pelo Estudo de Caso proposto. O modelo alocou 31 porcento dos servidores da ANAC na Região Sudeste do Brasil, 25 porcento na Região Nordeste, 17 porcento na Região Norte, 17 porcento na Região Sul e 10 porcento na Região Centro-Oeste; reduzindo em 66 porcento a quantidade total de inspetores. Obteve-se ainda uma matriz de distribuição de capacitações por agência da ANAC, de forma que o tomador de decisão possa analisar o perfil ótimo de habilitações dos funcionários de cada agência. Uma análise de sensibilidade foi conduzida para avaliar a flexibilidade do modelo, que se mostrou eficiente para aplicações em problemas reais. / [en] Over the last years, Research Operations development has become fundamental for Aviation Industry. In Brazil, the agency responsible for Civil Aviation inspection is the National Agency of Civil Aviation (ANAC). This work aims the development of an optimal personnel location-allocation model and application in a case study at ANAC in Safety Oversight context. One Literature Review has been done for gaps identification and to find the most recent solution techniques for facility location problems. The research objective has been achieved, and the proposed case study has validated the model. The model located 31 percent of ANAC personnel in Brazilian Southeast Region, 25 percent in Northeast Region, 17 percent in North Region, 17 percent in South Region and 10 percent in Central-West Region; decreasing in 66 percent the total quantity of allocated inspectors. A capacities matrix has been constructed with model results; decision-makers can analyze the optimal distribution of personnel capacities in each facility. Finally, a sensitivity analysis has been done to test the model flexibility, which prove the model is efficient for real problems application.

[pt] No Brasil, as distribuidoras (DisCos) devem suprir seu crescimento de carga por meio de contratos comercializados em leilões centralizados de Energia Nova, nos quais são leiloados contratos com entrega 4 anos a frente. No entanto, projetar a demanda de energia para vários anos à frente é muito desafiador, pois o consumo de energia é muito dependente da taxa de crescimento da economia, da possibilidade de surgimento de uma nova solução/tecnologia (geração solar distribuída) e da migração de consumidores cativos para o mercado livre. Embora as distribuidoras possam repassar os custos do excedente contratual de até 5 por cento nas tarifas de energia, esse limite tem se mostrado insuficiente desde que a última crise econômica no Brasil (2015) derrubou as expectativas de crescimento do consumo, deixando as distribuidoras com um superavit de contrato enorme. Essa situação tornou-se um problema para as distribuidoras, uma vez que esses contratos são liquidados no mercado spot, expondo-as ao preço spot, variável demasiadamente volátil no Brasil, e comprometendo assim a os seus fluxos de caixa. Neste contexto, criou-se o Mecanismo de Venda de Excedentes - MVE, um importante instrumento regulatório para gerenciamento do portfólio das distribuidoras. Por meio deste mecanismo as distribuidoras são capazes de vender, em um leilão centralizado, seus excedentes contratuais, reduzindo assim sua exposição ao mercado spot. Assim, este trabalho tem como objetivo propor uma metodologia para otimizar a estratégia das distribuidoras nos processamentos de MVE utilizando o conceito de Decisão sob Incerteza. Em outras palavras, o modelo indicará uma estratégia de venda de contratos no MVE, considerando o perfil de aversão ao risco do agente, avaliando os diferentes custos de oportunidade existentes neste processo de tomada de decisão. / [en] In Brazil, distribution companies (DisCos) must supply their expected load growth with contract purchases in centralized New Energy Auctions, in which commercial operation date – COD of generation projects being sold is (at least) 4 years ahead. Projecting energy demand for several years ahead is very challenging as energy consumption is very dependent on economy growth rate, the possibility of a surge of a new solution/technology (solar distributed generation) and the migration of captive consumers to the free market, to name a few. Even though distribution companies are allowed to pass through the costs of contract surplus of up to 5 percent in energy tariffs, this threshold was shown insufficient when the latest economic crisis in Brazil (2015) has knocked over consumption growth expectations, leaving distribution companies with huge contract surplus. This situation became a problem for the distribution companies since these contracts must be settled in the spot market, exposing them to the spot price, which is very volatile, and compromising their cash flow. In this context, the Mecanismo de Venda de Excedentes - MVE was created, an essential regulatory instrument to help distribution companies manage their energy portfolio. Through this mechanism, DisCos can sell in a centralized auction their contracts surplus, reducing their position in the spot market. This work aims to propose a methodology to optimize the distribution companies strategy in the MVE auctions using the theory of the Decision under Uncertainty. In other words, the model will indicate a strategy to sell contracts in the MVE, considering the agent s risk aversion profile, evaluating all the opportunity costs involving in this decision-making.

[pt] Descoberta de Processo significa determinar um modelo de processo a partir de um registro histórico de eventos de um processo de negócios. Muitos algoritmos de descoberta de processos tentam sintetizar uma rede de Petri que representa o registro localizando locais e arcos que relacionam as classes de eventos. Bergenthum et al (2007) e van der Werf et al. (2008) propõem formulações para este problema descobrir um place de cada vez, em que cada solução básica do conjunto de desigualdades representa um lugar candidato. Propomos uma formulação global de programação inteira que, dado um registro histórico, determina todos os places e arcos que definem uma rede de Petri de uma só vez. Este modelo é uma alternativa a seleção de locais, mas tem um problema de eficiência devido à grande quantidade de variáveis inteiras usadas. Também propomos um método de decomposição para o modelo ILP global para tratar cada place e suas restrições associadas como um subproblema separado. Conseguimos então executar o algoritmo em instâncias sintéticas grandes, o que é inédito para esta classe de mineradores de processo. / [en] Process Discovery amounts to determine a process model from an event log of a business process. Many process discovery algorithms try to synthesize a Petri net representing the log by finding places and arcs that relate the event classes. Bergenthum et al. (2007) and van der Werf et al. (2008) propose formulations for this problem discover one place at a time, in which each basic solution of the set of inequalities represents a candidate place. We propose a global integer programming formulation that, given a log, determines all places and arcs defining a Petri net. This model simplifies the selection of places but has an efficiency problem due to a large number of integer variables used. We also propose a decomposition method for the global ILP model to treat each place and their associated constraints as a separate sub-problem. We can run the algorithm on large synthetic instances, which is unprecedented for this kind of process miner.

[pt] Uma generalização do problema de roteamento de veículos (VRP) presente em aplicações práticas em portos e operações em minas é o objeto desta dissertação. Nesta variante do VRP cada cliente pode demandar diferentes tipos de veículos para cumprir tarefas colaborativamente. Nesta atividade, os veículos podem aguardar o início da operação no local porém, devem iniciar as tarefas ao mesmo tempo. O objetivo é determinar as rotas dos veículos disponíveis de modo a maximizar a soma (ponderada) dos clientes atendidos enquanto a distância total percorrida é minimizada. O caso específico onde todos os clientes são atendidos e a distância total percorrida é minimizada determina o problema central estudado nessa dissertação. Este caso particular pode ser visto como uma generalização direta do, muito estudado e conhecido problema de roteamento, VRP com janelas de tempo (VRPTW) onde a capacidade dos veículos é suficientemente grande. Esta escolha de um problema mais restrito é justificada por permitir uma clara comparação de sua dificuldade através da sua relação com o VRPTW. A partir da classificação dos casos de sincronização em problemas de roteamento proposta por (DREXL, 2012), denominamos o problema aqui estudado de Problema de Roteamento de Veículos com Janelas de Tempo e Sincronização exata da Operação (VRPTWEOS). Neste trabalho damos uma definição formal ao VRPTWEOS. Modelos de programação inteira são propostos e analisados. Também apressentamos métodos de resolução baseados na decomposição Dantzig-Wolfe, dos quais são derivados algoritmos exatos e aproximados. Com o propósito de avaliar a eficiencia desses algoritmos, foi criado um grupo de instancias de teste baseado no benchmark do Solomon para o VRPTW. O método usado para criar o conjunto de instancias de teste é descrito em detalhe. Experimentos computacionais sobre este conjunto de instancias mostraram que o método de resolução proposto é promissor para a resolução do VRPTWEOS. / [en] This dissertation addresses a generalization of the vehicle routing problem (VRP) that arises in real life applications in ports and mine operations. In this VRP variant, each customer may demand different types of vehicles to perform a task collaboratively. Vehicles are allowed to wait at the locations but they must start operating at the same time. The objective is to route the available vehicles while maximizing the (weighted) sum of served customers and minimizing the total distance traveled. The specific case where all customers must be served while minimizing the total distance traveled is the central problem here studied. This special case can be viewed as a straightforward generalization of, a well known and more specific routing problem, the VRP with time windows (VRTPTW) where the capacity of the vehicles is sufficiently large. We support this narrower scope by stating that it allows a clear comparison of the problem hardness by its relation to the VRPTW. Sticking to the classification of synchronization in vehicle routing proposed by (DREXL, 2012) we named this problem as the Vehicle Routing Problem with Time Windows and Exact Operation Synchronization (VRPTWEOS). In this work, a formal definition for the VRPTWEOS is provided. Integer programming models for this problem are proposed and analyzed. Furthermore, we propose a solution method based on the Dantzig-Wolfe decomposition for which exact and aproximated resolution algorithms are described. In order to test the performance of those algorithms, a group of benchmark instances for the VRPTWEOS was created on top of the Solomon benchmark for the VRPTW. The method used to create the benchmark instances is described in detail. Computational experiments over the mentioned set of instances showed that the proposed solution approach is a promising alternative for solving the VRPTWEOS.

[pt] Os Problemas de Roteamento de Veículos estão entre os problemas combinatoriais mais difíceis de se resolver à otimalidade. Eles foram propostos no final da década de 1950, e desde então eles têm sido amplamente estudados. O interesse deve-se a sua importância prática, bem como da dificuldade de se fornecer algoritmos eficientes para resolvê-los. Esta tese trata principalmente da resolução exata do Problema de Roteamento de Veículos com Capacidades (PRVC). Neste problema, um conjunto de clientes, cada um associado a uma demanda, deve ser atendido por uma frota de veículos. Todos eles têm o mesma capacidade e, inicialmente, estão localizados no mesmo depósito. Uma solução é um conjunto de rotas que começam e terminam no depósito e visitam cada cliente uma única vez. A restrição em uma rota é que a soma das demandas de seus clientes não exceda a capacidade do veículo. O objetivo é encontrar uma solução com um custo mínimo. Os melhores algoritmos exatos para o PRVC desenvolvidos nos últimos dez anos são baseados na combinação de geração de cortes e colunas. Alguns autores utilizaram apenas cortes sobre as variáveis da formulação original, com a finalidade de manter o subproblema de geração de colunas relativamente fácil. Outros puderam reduzir os limites duais utilizando também um número restrito de cortes expressos nas variáveis do problema mestre, parando de incluir tais cortes quando o subproblema tornavase proibitivamente difícil. Uma família eficaz de tais cortes são os Subset Row Cuts. Esta tese apresenta uma técnica para reduzir consideravelmente o impacto que tais cortes causam no subproblema de geração de colunas, permitindo assim que muito mais cortes sejam adicionados. O novo algoritmo Branch-Cut-and-Price proposto também incorpora e combina pela primeira vez vários elementos presentes em trabalhos anteriores, como enumeração de rotas, fixação de variáveis e strong branching. Todas as instâncias usadas em algoritmos exatos, com até 199 clientes, foram resolvidas à otimalidade. Além disso, algumas maiores, com até 360 clientes, apenas consideradas antes em métodos heurísticos, também foram resolvidas. / [en] Vehicle Routing Problems are among the most difficult combinatorial problems to solve to optimality. They were proposed in the late 1950 s and since then have been widely studied. This interest arises from their practical importance, as well as the difficulty of providing efficient algorithms to solve them. This thesis is mainly concerned with the exact resolution of the Capacitated Vehicle Routing Problem (CVRP). In this problem, a set of customers, each one associated to a demand, must be serviced by a fleet of vehicles. All vehicles have the same (limited) capacity and initially are located in the same central depot. A solution is a set of routes, starting and ending at the depot, that visit every customer exactly once. The only constraint on a route is that the sum of the demands of its customers does not exceed the vehicle capacity. The objective is to find a solution with minimum total cost. The best performing exact algorithms for the CVRP developed in the last 10 years are based in the combination of cut and column generation. Some authors only used cuts expressed over the variables of the original formulation, in order to keep the pricing subproblem relatively easy. Other authors could reduce the duality gaps by also using a restricted number of cuts over the Master LP variables, stopping when the pricing becomes prohibitively hard. A particularly effective family of such cuts are the Subset Row Cuts. This thesis introduces a technique for greatly reducing this impact on the pricing of these cuts, thus allowing much more cuts to be added. The newly proposed Branch-Cut-and-Price algorithm also incorporates and combines for the first time (often in an improved way) several elements found in previous works, like route enumeration, variable fixing and strong branching. All the instances used for benchmarking exact algorithms, with up to 199 customers, were solved to optimality. Moreover, some larger instances with up to 360 customers, only considered before by heuristic methods, were solved too.

[pt] Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.

[pt] Um algoritmo de alocação de freqüência eficiente deve considerar aspectos de propagação e detalhes de equipamento de modo a minimizar a relação a sinal interferência, e conseqüentemente, aumentar a eficiência do espectro. Essa dissertação tem o objetivo de propor uma melhor solução para alocação de freqüência nas rede TDMA e GSM, levando em consideração os aspectos citados. A abordagem utilizada é diferente das técnicas de alocação de freqüências usuais, que são baseadas na distância de reuso. O algoritmo proposto utiliza uma matriz que representa os aspectos de propagação (matriz de isolação) e uma matriz que representa os detalhes do equipamento (matriz de compatibilidade). A matriz de isolação mostra a relação sinal interferência que cada célula tem com as outras. Um estudo de como coletar os dados (seleção da rota no interior do setor) e de como trabalhar com os dados coletados foram realizados, objetivando-se ter matriz que melhor caracterizasse a rede utilizada. A matriz de compatibilidade mostra a distância em freqüência no qual se devem alocar os canais em uma mesma célula, células adjacentes e células co-sites. Os valores de espaçamento entre freqüências, sugeridos nesta dissertação, são valores práticos e dependem das técnicas utilizadas no planejamento e do equipamento utilizado em questão. O problema de alocação foi modelado com um problema inteiro. Uma heurística (divide and conquer) foi utilizada para particionar a rede em menores partes, em que o algoritmo branch and bound foi implementado. O algoritmo foi testado em duas redes com sessenta e trezentos e quarenta e oito setores respectivamente. As redes foram construída levando em consideração os dados topográficos e morfológicos da cidade de Brasília. / [en] An efficient frequency assignment algorithm should consider both propagation conditions and equipment details, in order to minimize the carrier-to-interference ratio (C/I) and, as a result, to increase spectrum efficiency. This dissertation proposes a way to obtain a better solution for frequency assignment in TDMA and GSM networks, taking into account propagation conditions and equipment details. The proposed approach is different from usual frequency assignment techniques based on reuse distance. A frequency assignment algorithm proposed uses one matrix that represents the propagation features (isolation matrix) and another which represents the equipment details (compatibility matrix). The isolation matrix shows the signal to interference ratio between any two sectors in the whole network. A survey to define how to collect the data ( selection of the route inside the sector) and how to work with data collected was developed, aiming to obtain the best matrix representation of the network. The compatibility matrix shows the frequency distance between channels in the same sector, adjacent sector and co-site sectors. The frequency space values used in this matrix are practical values, which depend upon the technique used on the planning and on the utilized hardware. The frequency assignment was formulated as an integer problem. An heuristic (divide and conquer) was used to split the network into smaller parts where an exact algorithm branch and bound was implemented. The algorithm was tested on two networks with 60 and 348 sectors respectively. The networks were built having the topographical and morphological data from Brasilia city. / [es] Un algoritmo eficiente de asignación de frecuencia debe considerar aspectos de propagación y detalles del equipo de modo tal que se minimize la relación señal-interferencia, y onsecuentemente, aumente la eficiencia del espectro. Esta disertación tiene como objetivo proponer una solución para la asignación de frecuencia en las redes TDMA y GSM, considerando los aspectos anteriormente citados. El enfoque utilizado difiere de las técnicas de asignación de frecuencias usuales, baseadas en la distancia de reuso. EL algoritmo propuesto utiliza una matriz que representa los aspectos de propagación (matriz de aislamiento) y una matriz que representa los detalles del equipo (matriz de compatibilidade). La matriz de aislamiento muestra la relación señal-interferencia que cada célula tiene con las otras. Se realiza un estudio de como recolectar los datos (selección de la ruta en el interior del sector) y de como trabajar con los datos recolectados, con el objetivo de obtener la matriz que mejor caracteriza la red utilizada. La matriz de compatibilidad muestra la distancia en frecuencia en la cual se deben alocar los canales en una misma célula, células adyacentes y células co-sites. Los valores de espacio entre frecuencias, sugeridos en esta disertación, son valores prácticos y dependen de las técnicas utilizadas en el planificación y del equipo utilizado. El problema de asignación fue modelado como un problema entero. Fue utilizada una heurística (divide and conquer) para particionar la red en menores partes, donde se implementó el algoritmo branch and bound. EL algoritmo fue probado en dos redes con sesenta y trezentos y quarenta y oito sectores respectivamente. Las redes fueron construidas considerando los datos topográficos y morfológicos de la ciudad de Brasilia.

[pt] Esta dissertação estuda formulações, algoritmos e métodos exatos para resolver instâncias do Problema de Alocação Generalizada (PAG) com uma separação de desigualdades (3, 0.5)-SRC que viabilize a enumeração de colunas. Este trabalho é motivado pela perspectiva de alcançar o estado-da-arte com resultados competitivos comparáveis às melhores soluções encontradas na literatura por Avella (2010) e Michelon (2012). A pesquisa abrange métodos exatos e heurísticas, com ênfase no estudo que aborda a decomposição de Dantzig-Wolfe, o algoritmo de geração de colunas, a estabilização de colunas por meio da ponderação de duais proposto por Wentges (1997) e a enumeração de colunas habilitada pela minimização do gap decorrente do algoritmo de price-and-cut. O algoritmo de price-and-cut desenvolvido recorre à geração de colunas (pricing) aliada à separação de (3, 0.5)-SRCs para aumentar o lower bound gerado, assim minimizando o gap. A geração de colunas implementada é inspirada no algoritmo de Savelsbergh (1997); e a separação de (3, 0.5)-SRCs é motivada pelo trabalho de Jepsen (2008) e pelo algoritmo branch-cut-andprice proposto por Poggi e Uchoa (2016) para o CVRP. De acordo com os experimentos computacionais, as desigualdades adotadas são capazes de reduzir o gap suficientemente para viabilizar a enumeração de colunas em diversas instâncias do PAG com até 200 tarefas e 20 máquinas. O método utilizado obteve resultados compatíveis às melhores soluções conhecidas, enumerando todas as colunas necessárias para cobrir o gap determinado pelo price-and-cut. Esse resultado incentiva futuras pesquisas para estender a aplicação do algoritmo a instâncias maiores e mais difíceis. / [en] This dissertation deals with formulations, algorithms and exact methods for solving the well-known Generalized Assignment Problem (GAP) through a price-and-cut approach with the separation of (3, 0.5)-SRC inequalities in order to improve column enumeration feasibility and efficiency. This work is motivated by the perspective of reaching state-of-the-art performance, attaining competitive results which are comparable with the best known solutions found in the literature by Avella (2010) and Michelon (2012). This research was build on exact methods and some heuristics with emphasis on the Dantzig- Wolfe decomposition, the column generation algorithm, the stabilization through weighted Dantzig-Wolfe decomposition proposed byWentges (1997) and finally the column enumeration motivated by the gap minimization reached through the price-and-cut algorithm. The price-and-cut algorithm proposed here resort to column generation (pricing) combined with the separation of (3, 0.5)-SRC cuts in order to increase the generated lower bound, thus minimizing the attained gap. This column generation algorithm follows the work of Savelsbergh (1997); and the separation of (3, 0.5)-SRCs is formulated by Jepsen (2008) and motivated by the branch-cut-and-price algorithm proposed by Poggi and Uchoa (2016) for the CVRP. According to computational experiments, the adopted inequalities are capable of sufficiently reducing the gap, assuring the feasibility of column enumeration for several GAP instances with up to 200 tasks and 20 machines. This method achieved expressive results, compatible with the best known solutions, enumerating all the necessary columns to cover the gap found by the price-and-cut. Therefore, these results motivate future research towards the extension of the method s applicability to larger and more complex instances.