[pt] O planejamento e a gestão de atividades esportivas é uma área promissora e pouco explorada para aplicações de Pesquisa Operacional. Os problemas nesta área são em geral de formulação simples e alcançam grande difusão nos meios de comunicação. Embora sua formulação seja simples, em geral estes problemas são difíceis de serem resolvidos em termos computacionais. Os resultados de muitos trabalhos acadêmicos nesta área têm sido aceitos como soluções para problemas reais e várias soluções vem sendo implementadas na prática. Esta tese tem como objetivo principal estudar dois tipos de problemas que surgem na área de esportes: a programação de tabelas e os problemas da classificação. A programação de tabelas para competições esportivas é uma tarefa difícil, na qual diversas técnicas de otimização combinatória têm sido aplicadas. Nesta tese, formula-se o Problema do Torneio com Viagens Espelhado como um problema de otimização em grafos. O problema é resolvido utilizando- se algoritmos aproximados. Apresentam-se duas heurísticas para este problema. A primeira é muito rápida e serve para fornecer soluções iniciais para a segunda, que é capaz de obter soluções de boa qualidade em tempos razoáveis. São deduzidos limites duais para um tipo particular de instâncias. Estes limites permitem provar a otimalidade das soluções obtidas heuristicamente para instâncias muito maiores do que as maiores instâncias resolvidas na literatura. Por ultimo, é apresentado um modelo de programação linear inteira para o problema, ao qual são acrescentadas desigualdades válidas. Os problemas da classificação visam obter condições, necessárias e suficientes, para a classificação de uma determinada equipe para as finais de um campeonato em relação ao número de pontos a ser obtido. São apresentados modelos de programação linear inteira que permitem resolver estes problemas no contexto do Campeonato Brasileiro de Futebol. / [en] Sports management is a very attractive and not very explored area for applications of Operations Research. Problems in this area use to have simple formulations and reach a big coveragge by the media. Although their formulations are simple, in general these problems are difficult to be solved in computational terms. The results of many academic works in this area have been accepted as solutions for real problems and some solutions are being implemented. This thesis has the main objective of studying two types of problems that appear in the sports area: the fixture creation and the qualification problems. Fixture creation (also known as sport scheduling) for sport competitions is a difficult task, in which several combinatorial optimization techniques has been applied. In this thesis, the Mirrored Traveling Tournament Problem is formulated as a graph optmization problem. The problem is solved using approximation algorithms. Two heuristics are introduced for this problem. The first one is very fast and is used to supply initial solutions for the second one which is able to obtain high quality solutions in reasonable computation times. Dual limits are deduced for a particular type of instances. These limits allow to prove the optimality of the heuristically abtained solutions for instances that are much bigger than those soved in the literature. Finally, an integer programming model is introduced in wich valid inequalities are added. The qualification problems aim to obtain necessary and sufficient conditions for the playoffs qualification of a given team in terms of the number of points to be obtained. Integer programming models are introduced which allow solving these problems in the context of the Brazilian Football Championship.

[pt] O problema de Roteamento de Veículos com restrição de capacidade (CVRP) é um dos problemas mais estudados em Otimização Combinatória. Sendo uma generalização imediata do conhecido problema do Caixeiro Viajante, o CVRP tem atraído a atenção dos pesquisadores mais proeminentes da área desde os anos 60. Um dos algoritmos mais importantes para a sua resolução foi proposto no início dos anos 80 quando um algoritmo utilizando uma relaxação Lagrangeana particularmente adequada provou ser bastante superior aos algoritmos contemporâneos. Este algoritmo sugeriu a utilização de técnicas de geração de colunas que, nos anos seguintes até o início dos anos 90, assumiram o rótulo de melhor algoritmo para o CVRP. Finalmente, em meados dos anos 90, algoritmos de planos de corte apresentaram resultados que convenceram a comunidade de que esta deveria ser a abordagem para resolver os problemas mais difíceis de CVRP. Esta dissertação apresenta uma revisão deste algoritmos anteriores e propõe um formulação que permite reunir o melhor deles. O algortimo resultante, que pode ser rotulado como de branch-and-cut-and-price, trabalha com um número exponencial de variáveis e restrições que definem um espaço relaxado de soluções que corresponde à interseção dos espaços de solução relaxados utilizados pelos algoritmos anteriores. Esta dissertação também descreve um implementação especial do algoritmo de programação dinâmica para resolução do problema de geração de colunas. Estratégias para fazer um branching robusto também são discutidas. Tudo isso permite construir um algoritmo que é capaz de ter uma boa performance quando aplicado a diferentes classes de instâncias. A experiência computacional mostrou que a abordagem proposta obtém limites inferiores consistentemente melhores que os dos algoritmos anteriores. Mais ainda, permite resolver em tempo hábil diferentes tipos de instâncias de até 135 vértices, incluindo 18 que foram resolvidas pela primeira vez. / [en] The Capacitated Vehicle Routing problem (CVRP) has been one of the most studied problems in the field of Combinatorial Optimization. A straight forward generalization of the popular Travelling Salesperson problem, the CVRP has drawn attention of the most prominent researchers since the early 60`s. One of the most important algorithms appeared in the early 80`s when a suitable Lagrangean relaxation algorithm has demonstrated to be far better than the contemporary ones. This algorithm suggested the use of column generation algorithms that succeeded to become the best ones in the late 80`s and early 90`s. Finally, in the mid 90`s, cutting plane methods presented results that convinced the community that this should be the approach for solving the hardest CVRP problems. This dissertation presents an overview of those early algorithms and proposes a formulation that allows uniting the best contributions of them. The resulting algorithm, labeled as a branch-and-cut-and-price algorithm, deals with exponentially many variables and constraints that define a relaxed solution space that is the intersection of the relaxed solution spaces considered in the previous algorithms. The dissertation also describes a specially devised dynamic programming algorithm to solve the column generation subproblem and discusses robust branching strategies that altogether allowed to build an algorithm that perfoms well on several different classes of instances. The computational experience has shown that the approach here proposed leads to lower bounds superior than the previous ones. Moreover, it allowed to consistently solve instances with up to 135 vertices, including 18 that were solved for the first time.

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

Uma abordagem de teste estrutural de integração par-a-par para programas OO e OA escritos em Java e AspectJ é apresentada. A finalidade dessa abordagem é descobrir defeitos que possam existir na interface entre os pares de unidades que se relacionam em um programa. Para programas OO este tipo de teste envolve testar a interação entre os pares de métodos. Já para programas OA, o teste estrutural de integração par-a-par envolve testar a interação entre os seguintes pares de unidades: método-método, método-adendo, adendo-método e adendo-adendo. Para efetuar o teste estrutural de integração par-a-par deve-se considerar todo o fluxo de execução (fluxo de controle e de dados) que ocorre entre a unidade chamadora e a unidade chamada. Para isso é definido o grafo Def-Uso Par-a-Par (PWDU) que é uma abstração formada pela integração dos grafos Def-Uso Orientado a Aspectos (AODU) da unidade chamadora e da unidade chamada. Além disso, são propostos três critérios para derivar requisitos de teste para pares de unidades. Dentre eles, dois critérios são baseados em fluxo de controle: todos-nós-integrados e todas-arestas-integradas; e um critério é baseado em fluxo de dados: todos-usos-integrados. Uma ferramenta que apóia o teste estrutural de unidade de programas OO e OA escritos em Java e AspectJ, chamada JaBUTi/AJ, foi estendida para dar apoio à abordagem de teste de integração proposta. Exemplos de usos são discutidos para explicar a aplicação da abordagem / A pairwise integration structural testing approach for OO and AO programs implemented with Java and AspectJ is presented. The purpose of this approach is to find faults that may exist in the interface between the pairs of units that relate in a program. For OO programs this type of testing involves testing the interaction among pair of methods. For AO programs, the pairwise integration structural testing involves testing the interaction among the following pairs of units: method-method, method-advice, advice-method and advice-advice. To perform the pairwise integration structural testing, all the execution flow (control and data flow) that happens between the caller and the called unit must be considered. For this, it is defined the PairWise Def-Use graph (PWDU) that is an abstraction formed by the integration of the Aspect-Oriented Def-Use (AODU) graphs of the caller and called unit. Additionally, three new criteria to derive test requirements for pairs of units are proposed. Amongst them, two criteria are based on control flow: all-integrated-nodes and all-integrated-edges; and one criterion is based on data flow: all-integrated-uses. A tool that supports unit structural testing of OO and AO programs implemented with Java and AspectJ, called JaBUTi/AJ, was extended in order to support the proposed integration testing approach. Examples are discussed in order to explain the application of the approach