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

[pt] Esta dissertação apresenta uma solução que permite a geração automática de exemplos de uso a partir da descrição textual de casos de uso. Os casos de uso descrevem especificações em um nível de formalização suficiente para a geração dos exemplos. Um exemplo gerado é um texto em linguagem natural que é o resultado da paráfrase de um possível comportamento do software, extraído de um caso de uso e aplicado a um contexto real, em que atores são convertidos em personagens fictícios e os atributos são valorados de acordo com as regras de negócios especificadas no caso de uso. O formato proposto para a construção de exemplos tem como objetivo permitir que clientes possam ler, entender e julgar se o comportamento que está sendo proposto é o desejado. Com isso é esperado que o próprio cliente possa validar as especificações e que, quando defeitos forem encontrados, a especificação possa logo ser corrigida e refletida de volta nos exemplos. Ao mesmo tempo a especificação formalizada na forma de um caso de uso auxiliará desenvolvedores a criar soluções mais próximas do correto por construção, quando comparado com especificações textuais convencionais. / [en] This master s dissertation presents a solution for the automatic generation of examples of use from the textual description of use cases. Use cases describe specifications in a sufficiently formal way that is enough to automatically generate usage examples. A generated example is a text in a natural language which is the paraphrase of one possible manner to use the software, extracted from the use case and applied to a real context where actors are converted into fictitious personas and attributes are valued according to the business rules specified in the use case. The proposed format to present the example aims to allow clients to read, to understand and to judge whether the expressed behavior is in fact what he wants. With this approach, it is expected that the customer himself can approve the specifications and when defects are found, so the specification can quickly be corrected and reflected in the examples. At the same time, the formalized specification in the form of a use case will help developers create solutions that are by construction closer to the correct one when compared to conventional textual specifications.

[pt] O primeiro estágio na linha de produção de um sistema de geração procedural de cidades é, tipicamente, a geração da malha rodoviária. Este trabalho apresenta um algoritmo para a geração de malhas rodoviárias em paralelo na GPU usando um modelo de execução baseado em filas de trabalho. Esse algoritmo recebe parâmetros declarativos, juntamente com mapas geográficos e sócio estatísticos, e produz uma representação em alto nível de uma malha rodoviária urbana. / [en] The first stage in the pipeline of a procedural city generation system is typically the generation of the road network. This work presents a parallel algorithm for road networks generation on the GPU, using a work-queue based execution model. This algorithm receives declarative parameters along with geographic and socio-statistical maps and produces a high level representation of an urban road network.

[pt] Este trabalho apresenta uma metodologia para geração de malhas adaptativas de elementos finitos 2D e 3D usando modeladores geométricos com multi-regiões e superfícies paramétricas. A estratégia adaptativa adotada é fundamentada no refinamento independente das curvas, superfícies e sólidos. Inicialmente as curvas são refinadas, no seu espaço paramétrico, usando uma técnica de partição binária da curva (binary-tree). A discretização das curvas é usada como dado de entrada para o refinamento das superfícies. A discretização destas é realizada no seu espaço paramétrico e utiliza uma técnica de avanço de fronteira combinada com uma estrutura de dados do tipo quadtree para gerar uma malha não estruturada de superfície. Essas malhas de superfícies são usadas como dado de entrada para o refinamento dos domínios volumétricos. A discretização volumétrica combina uma estrutura de dados do tipo octree juntamente com a técnica de avanço de fronteira para gerar uma malha sólida não estruturada de elementos tetraédricos. As estruturas de dados auxiliares dos tipos binary-tree, quadtree e octree são utilizadas para armazenar os tamanhos característicos dos elementos gerados no refinamento das curvas, superfícies e regiões volumétricas. Estes tamanhos característicos são definidos pela estimativa de erro numérico associado à malha global do passo anterior do processo adaptativo. A estratégia adaptativa é implementada em dois modeladores: o MTOOL (2D) e o MG (3D), que são responsáveis pela criação de um modelo geométrico, podendo ter, multi-regiões, onde no caso 3D as curvas e superfícies são representadas por NURBS. / [en] This work presents a methodology for adaptive generation of 2D and 3D finite-element meshes using geometric modeling with multi- regions and parametric surfaces. The adaptive strategy adopted in this methodology is based on independent refinements of curves, surfaces and solids. Initially, the model´s curves are refined using a binary-partition algorithm in parametric space. The discratizetion of these curves is used as input for the refinement of adjacent surfaces. Surface discretization is also performed in parametric space and employs a quadtree-based refinement coupled to an advancing-front technique for the generation of an unstructured triangulation. These surface meshes are used as input for the refinement adjacent volumetric domains. Volume discretization combines an octree refinement with an advancing-front technique to generate an unstructural mesh of tetrahedral elements. In all stages of the adaptive strategy, the refinement of curves, surface meshes and solid meshes is based on estimated numerical errors associated to the mesh of the previous step in the adaptive process. In addition, curve and surface refinement takes into account metric distortions between parametric and Cartesian spaces and high curvatures of the model´s geometric entities. The adaptive strategies are implemented in two different modelers: MTOOL (2D) and MG (3D), which are responsible for the creation of a geometric model with multi-regions, where for case 3D the curves and surfaces are represented by NURBS, and for the interactive and automatic finite-element mesh generation associated to surfaces and solid regions. Numerical examples of the simulation of engineering problems are presented in order to validate the methodology proposed in this work.

[pt] O uso seqüencial de energia elétrica e energia térmica a partir da energia química do mesmo combustível tem sido estudado para melhorar o custo benefício de uma geração distribuída. O objetivo deste estudo é determinar o mercado potencial desta tecnologia na região de influência da concessionária local de energia elétrica. Para alcançar este objetivo, foi necessário avaliar o desempenho de um sistema de cogeração com uma microturbina fornecendo potência elétrica e energia térmica através dos gases de exaustão que aquecem água para o ginásio esportivo da PUC-Rio. O sistema está configurado por uma microturbina, uma caldeira de recuperação, um reservatório térmico (boiler) e uma caixa para alimentação de água fria. Resultados obtidos de testes de curta duração, através de uma metodologia desenvolvida, para a avaliação do desempenho do sistema de cogeração na produção de energia elétrica e térmica, são apresentados. Os testes foram realizados para potências elétricas de 100, 75, 50 e 25 % da carga máxima da microturbina. Em adição, testes para avaliação do desempenho ao longo do tempo em função das variações da carga e das condições ambientais foram estudados. Além disso, através de uma metodologia desenvolvida, mostram-se os resultados nos cálculos de incerteza dos parâmetros analisados. Dados de consumo de energia elétrica em janeiro de 2003, de cerca de 8000 consumidores na área de concessão da LIGHT SESA, em diferentes classes tarifárias, atualizadas para 2007, foram utilizados com a metodologia desenvolvida para estimar o mercado potencial de energia elétrica na região de influência da concessionária local de energia elétrica em 384,5 MW e 20415 MWh/mês, considerando uma taxa interna de retorno mínimo de 15% a.a. Foi mostrado que o elevado custo da microturbina é uma barreira para sua introdução no mercado. Entretanto, a cogeração pode colaborar substancialmente para melhorar o custo benefício. Estas conclusões foram obtidas a partir do tempo de retorno do investimento no sistema pelos consumidores analisados. / [en] The sequential use of electric energy and thermal energy from the chemical energy of the same fuel has been studied to improve the cost benefit of a distributed generation. The objective of this study is to evaluate the potential market of this technology in the region of influence of the local utility of electric energy.utility company (LIGHT). In order to attain this objective, it was necessary to evaluate the performance of a micro turbine based cogeneration system used for supplying electrical and thermal energy to PUC-RIO´S Gymnasium. The system consists of a microturbine, a heat recovery boiler, and a cold water feeding reservoir. The short duration test results are presented for the evaluation of the cogeneration system performance for the production of electric and thermal energy. The tests were carried on for 100, 75, 50 and 25% micro turbine electric energy generation loads. Time performance of the micro turbine was also studied. Moreover, a methodology was shown to calculate the uncertainty of measurements of several performance parameters. The micoturbine marked potential was estimated by analyzing the consumption of about 8000 clients in January 2003, updating the tariffs to 2007, resulting in 384,5 MW and 20415 MWh/month, considering a minimum internal rate of return of investiment of 15% per year, during a 15 year period. It was concluded that the microturbine cost is still a barrier to its market penetration. Cogeneration can be used to improve the cost benefit of the system.

[pt] O uso de tecnologias para incrementar a geração distribuída de energia elétrica, particularmente microturbinas a gás, tem aumentado ultimamente devido à crise de energia que muitos países, como o Brasil têm passado o que é um incentivo à produção independente de energia elétrica. Procedimentos têm sido desenvolvidos para verificar os dados de desempenho de microturbinas, com objetivo de comissionamento. Quando alguém compra um sistema de geração de energia, sua partida pode apenas ser efetivada quando os dados do fabricante concordam com os de projeto, dentro de uma faixa de incerteza acordada, qualificando, portanto, estudos de viabilidade anteriormente realizados. Muitos procedimentos são detalhados para verificar os dados de desempenho sob condições de teste, extrapolando-os para outras diferentes. Potência, consumo de gás, emissão dos gases, qualidade da energia elétrica (incluindo distorção harmônica e frequência) estão entre os parâmetros normalmente medidos. A freqüência de aquisição de dados é normalmente especificada para atender as características de desempenho do equipamento sob condições estáveis de teste. Também, a incerteza dos instrumentos de medição é normalmente especificada, sem qualquer referência à incerteza expandida dos parâmetros calculados, que são usados para caracterizar seu desempenho. Este trabalho descreve um método para avaliação dos dados de desempenho de uma microturbina a gás, juntamente com uma metodologia para calcular a incerteza dos parâmetros que caracterizam seu desempenho, com objetivos de comissionamento, a partir da incerteza dos instrumentos de medição, e fazendo uma análise crítica dos objetivos de medição a serem alcançados. A metodologia é baseada nos conceitos metrológicos mais recentes, de forma que resultados confiáveis possam ser alcançados, utiliza condições de referência, estabelecidas por norma internacional [ISO-2314, 1973], para especificação dos dados de desempenho dos equipamentos, com objetivo de comparação, e segue as diretrizes da U.S. Enveronmental Protection Agency para especificação do desempenho a ser alcançado. / [en] The use of technologies for increasing distributed electric energy generation, particularly gas fired microturbines, has been lately growing due to the energies crisis many countries, including Brasil, have experienced, which is an incentive to an independent electric energy production. Procedures have been developed to check microturbine performance data for commissioning purposes. When somebody buys an energy production plant, its start-up can only be accomplished when manufacturers data matches the design data within an agreed uncertainty band, thus qualifying the previously made feasibility studies. Many procedures are detailed for checking the performance data under testing conditions, and extrapolating them for different ones. Power, gas consumption, gas emissions, electric energy quality (including harmonic distortion and frequency) are among the usually measured parameters. Data acquisition frequency is usually specified to match specified equipment behaviour under stable test conditions. Also, the uncertainty of the measurement instruments are usually specified, without, however, defining the expanded uncertainty of the calculated parameters, which are used to characterize their performance. This work presents a method for evaluating the gas fired microturbine performance data for electric energy generation, together with a methodology for calculating the uncertainty of parameters that characterize its performance for commissioning purposes, starting up from the uncertainty of the measurement instruments, and making a critical analysis of the measurement goals. The methodology is based on most recently used metrology concepts, so that reliable results can be achieved, uses ISO reference conditions for specifying equipment performance data for comparison purposes and follows U.S. Environment Protection Agency directions for specifying performance goals.

[pt] O Setor de energia elétrica no Brasil vem sofrendo fortes mudanças estruturais, cujo principal objetivo é criar um caráter competitivo para permitir ao setor crescer não mais por investimentos estatais, mas sim pelas mãos do capital privado. Com isso, espera-se que a oferta possa acompanhar a demanda crescente nos últimos anos, devido a falta de investimentos no setor, e fazer com que o risco de déficit de carga no futuro diminua. O Programa Prioritário de Termelétricas, lançado pelo governo federal, vai aumentar a oferta de energia no país com a construção de usinas termelétricas, aproveitando o fato da disponibilidade de gás natural existente, e com isso aumentará a participação de geração térmica na matriz energética brasileira. Essa mudança vai conferir mais confiabilidade ao parque gerador de energia, diminuindo o risco de déficit energético pela redução do nível de água dos reservatórios das usinas hidrelétricas. Além disso, as usinas termelétricas são uma alternativa de curto prazo para o Brasil, pois devido ao reduzido prazo de construção, permitiria o aumento da oferta durante a transição para o mercado competitivo, minimizando com isso os riscos de déficit no futuro. As termelétricas, nessa nova estrutura do setor elétrico brasileiro, podem se declarar flexíveis ou inflexíveis. Uma termelétrica flexível é aquela onde sua energia pode ser comercializada no Mercado Atacadista de Energia (MAE), logo ficando sujeita a volatilidade do mercado spot, mas podendo obter grandes lucros. Uma termelétrica inflexível é aquela onde toda sua energia é comercializada mediante contratos bilaterais, ou seja, a energia gerada não é comercializada no MAE. Isto reduz as incertezas, mas também reduz as oportunidades de grandes lucros. A maior incerteza de um projeto do setor elétrico brasileiro é o preço da energia elétrica que em países onde este setor foi reestruturado, como o Brasil, é determinado através do custo marginal de curto prazo (CMCP), por um modelo de otimização energética não publicado ao mercado. Em vista disso, essa dissertação se propõe a formular um modelo para os preços de energia elétrica no Brasil, avaliar uma planta de geração térmica utilizando a Teoria de Opções Reais aliada a técnica de simulação de Monte Carlo e comparar os resultados com os obtidos por Alessandro de Lima Castro em sua dissertação de Mestrado defendida em abril de 2000 cujo título é Avaliação de Investimento de Capital em Projetos de Geração Termoelétrica no Setor Elétrico Brasileiro Usando Teoria das Opções Reais. / [en] The Brazilian Electricity Sector has experienced strong structural changes, whose main objective is to create a competitiveness character to allow for the sector to grow not more for state investments, but now for the hands of the private capital. So, it is expected that supply can meet the growing demand in the last years, due to the lack of investments in the sector, and consequently reduce the risk of load deficit in the future. The Emergency Program of Thermal Plants, introduced by the federal government, will increase the offer of energy in the country with the construction of thermal plants, taking advantage of the availability of natural gas, and thus, will increase the participation of thermal generation in Brazil. That change will give more reliability to the Brazilian Electric System, reducing the risk of energy deficit due to the reduction of the level of water in the reservoirs of the hydro plants. Besides, thermal plants is a short-term alternative to Brazil, because its construction term is shorter than that of hydro plants, so this will increase the offer of energy during the transition for the competitive market, and so reducing the risk of load deficit in the future. Thermal Plants, in that new structure of the Brazilian Electric Sector, can be declared flexible either or inflexible. A flexible thermal plant is that where its energy can be negotiated in a WholeSale Energy Market, and so being subjects the volatility of the spot market, but it could obtain great profits. An inflexible thermal plant is that where its whole energy is negotiated by through bilateral contracts, that is, the energy generated is not negociated in the WholeSale Energy Market. This reduces uncertainties, but it also reduces the opportunities of great profits. The largest uncertainty of a project of the Brazilian electric sector is the price of electricity, and in countries where this sector was restructured, like in Brazil, it is determined through the short run marginal cost (SRMC), for energetic otimization model not published to the market. Thus, this dissertation intends to formulate a model for the price of electricity in Brazil, to evaluate a thermal plant using Real Options Theory and Monte Carlo simulation, and to compare the results with CASTRO´s dissertation: Evaluation of Capital Investment in Thermoelectric Generation Projects in the Brazilian Electricity Sector Using Real Options Theory. / [es] El Sector de energía eléctrica en Brasil ha sufrido fuertes cambios extructurales, con el objetivo de crear un carácter competitivo que permita el crecimiento de este sector, en manos del capital privado y no más por inversiones estatales. Con esto, se espera que la oferta consiga acompañar la demanda cresciente en los últimos años, debido a la falta de inversiones en el sector, y conseguir que el riesgo de déficit de carga en el futuro disminuya. El Programa Prioritario de Termoeléctricas, lanzado por el gobierno federal, pretende aumentar la oferta de energía en el país con la construcción de centrales termoeléctricas, aprovechando la disponibilidad de gas natural existente. Como consecuencia aumentará la participación de la generación térmica en la matriz energética brasilera. Este cambio dará mayor confiabilidad al parque generador de energía, diminuyendo el riesgo de déficit energético por la reducción del nível de agua de los depósitos de las centrales hidroeléctricas. Además, las centrales termoeléctricas constituyen una alternativa de corto plazo para Brasil que, gracias al reducido plazo de construcción, permitiría el aumento de la oferta durante la transición para el mercado competitivo, minimizando así, los riesgos de déficit en el futuro. Las termoeléctricas, en esta nueva extructura del sector eléctrico brasilero, pueden declararse flexibles o inflexibles. Em una termoeléctrica flexible la energía puede ser comercializada en el Mercado Atacadista de Energía (MAE), sujetándose a la volatilidad del mercado spot, pero pudiendo obtener grandes lucros. Una termoeléctrica inflexível comercializa toda su energía mediante contratos bilaterales, o sea, la energía generada no se comercializa en el MAE. Esto reduce los riesgos, pero también reduce las oportunidades de grandes lucros. El mayor riesgo de un proyecto del sector eléctrico brasilero es el precio de la energía eléctrica que, en países donde este sector fue reextructurado, (como en Brasil) se determina a través del costo marginal de corto plazo (CMCP); a través de un modelo de optimización energética no publicado al mercado. Esta disertación se propone formular un modelo para los precios de energía eléctrica en el Brasil, evaluar una planta de generación térmica utilizando la Teoría de Opciones Reales aliada a la técnica de simulación de Monte Carlo; y comparar nuestros resultados con los obtenidos por Alesandro de Lima Castro en su disertación de Mestrado defendida en abril de 2000 bajo el título Evaluación de Inversión de Capital en Proyectos de Generación Termoeléctrica en el Sector Eléctrico Brasilero Usando Teoría de las Opciones Reales.

[pt] O estudo procura identificar as formas pelas quais o festival de música intitulado Rock in Rio foi capaz de atravessar gerações e, no Rio de Janeiro, ao longo de mais de trinta anos (1985-2017) e com futuros eventos confirmados, se manter pertinente junto às diferentes juventudes que vivenciaram - e ainda vivenciam - suas diversas edições. Para isso se desdobra, primeiramente, em uma análise sobre os festivais contemporâneos enquanto importantes difusores da música na atualidade, além relevantes mediadores do encontro presencial e da convivência social; e, ainda, como se tornaram símbolos de valores tipicamente associados ao conceito de juventude que, no Brasil, vieram ao encontro de um cenário local que propiciou o surgimento do Rock in Rio. Na sequência, o estudo apresenta informações sobre a abrangência deste festival, junto a aportes teóricos onde dialogam os campos da comunicação, história e memória que refletem o contexto de sua realização. Por último, são apresentados os achados das duas etapas compreendidas no trabalho de campo: (a) a observação participante realizada durante a edição de setembro de 2017 do Rock in Rio; e (b) as entrevistas em profundidade com integrantes da audiência da primeira edição do festival, no ano de 1985, e com representantes da atual geração de jovens, no que concerne à faixa etária, que passaram a frequentá-lo a partir de 2011. Ambas tiveram como objetivo entender o valor simbólico do Rock in Rio para as distintas gerações que compõem a sua audiência, fator que se mostrou intrínseco à longevidade do festival. / [en] The study aims to identify the ways by which the music festival entitled Rock in Rio was able to cross generations in the city of Rio de Janeiro and make itself relevant along with the distinct youths who have lived and experienced its various editions for more than thirty years (1985-2017) with future events already confirmed. To this end, the study presents an analysis of contemporary festivals as one of the main broadcasters of music in the present time, besides being relevant mediators of the face-to-face meeting and the social coexistence; and also how they became symbols of values typically associated with the concept of youth, which have found particular circumstances in Brazil that led to the emergence of Rock in Rio. The study then presents some institutional information about this music festival, together with theoretical contributions on the fields of communication, history and memory that reflect the context of its accomplishment. Finally, the findings of the two stages included in the fieldwork are presented: (a) a research carried out during the September 2017 edition of Rock in Rio; and (b) in-depth interviews with members of the audience of this festival s first edition, in 1985, together with current young people, regarding the age group, who accompanied its most recent editions (from 2011). Both phases were aimed at understanding the symbolic value of Rock in Rio for the distinct generations that make up its audience, something that was perceived as intrinsic to the festival s longevity.

[pt] O Capacitated Vehicle Routing Problems (CVRP) é uma versão seminal do problema de roteamento de veículos, um clássico problema em Pesquisa Operacional. Introduzido por Dantzig e Ramser, o CVRP generaliza o Traveling Salesman Problem (TSP) e o Bin Packing Problem (BPP). Problemas de roteamento aparecem em diversas aplicações no mundo real, geralmente no contexto de diminuição de custos, emissão de poluentes ou energia dentro das atividades relacionadas ao transporte. De fato, estes custos podem ficar entre 5 por cento e 20 por cento do custo total do produto. Por isto, qualquer economia nos custos de roteamento pode ser relevante. O CVRP é definido da seguinte maneira: dado um conjunto de n mais 1 localidades - um depósito e n clientes - as distâncias entre cada par de localidades, as demandas inteiras associadas a cada cliente e a capacidade do veículo, quer se obter um conjunto de rotas que comecem no depósito, visitem cada cliente apenas uma vez e retornem ao depósito. A distâncias percorrida deve ser mínima e a soma das demandas dos clientes presentes em cada rota não pode exceder a capacidade do veículo. Este trabalho considera que o número de veículos disponíveis é conhecido. Algoritmos no estado da arte para encontrar e provar que uma solução é ótima, para o CVRP, calculam seus limites inferiores através de geração de colunas e depois os melhoram com a adição de planos de corte. As colunas geradas podem ser rotas elementares, onde obrigatoriamente cada cliente é visitado somente uma vez, ou uma relaxação desta obrigação com o uso de q-rotas ou ng-rotas, que diferem apenas em como é permitido que um cliente seja revisitado dentro de uma mesma rota. Já os cortes são classificados como robustos, aquele que são definidos sobre as variáveis dos arcos, e não robustos (ou fortes), que são os definidos sobre as variáveis do problema mestre da geração de colunas. O termo robusto, usado acima, se refere a como a adição do corte modifica a eficiência da resolução do problema de pricing. Além do descrito acima, o algoritmo exato mais eficiente para o CVRP usa muitos elementos, o que torna sua replicação uma tarefa difícil e longa. O objetivo deste trabalho é determinar o quão bom são os limites inferiores obtidos com geração de colunas de ng-rotas usando apenas cortes de capacidade e os recentes subset row cuts de memória limitada. Além disto, é avaliado o ganho conseguido com a consideração deste tipo de corte forte e as combinações com outras técnicas, como por exemplo, Decremental Space State Relaxation (DSSR), Completion Bounds, ng-rotas e cortes de capacidade sobre a formulação de Set Partitioning. Extensos experimentos computacionais são apresentados em conjunto com a análise dos resultados obtidos. / [en] The Capacitated Vehicle Routing Problem (CVRP) is the seminal version of the vehicle routing problem, a classical problem in Operational Research. Introduced by Dantzig e Ramser, the CVRP generalizes the Traveling Salesman Problem (TSP) and the Bin Packing Problem (BPP). In addition, routing problems arise in several real world applications, often in the context of reducing costs, polluent emissions or energy within transportation activities. In fact, the cost with transportation can be roughly estimated to represent 5 per cent to 20 per cent of the overall cost of a delivered product. This means that any saving in routing can be much relevant. The CVRP is stated as follows: given a set of n plus 1 locations - a depot and n customers - the distances between every pair of locations, integer demands associated with each customer, and a vehicle capacity, we are interested in determining the set of routes that start at the depot, visits each customer exactly once and returns to the depot. The total distance traveled by the routes should be minimized and the sum of the demands of customers on each route should not exceed the vehicle capacity. This work considers that the number of available vehicles is given. State of the art algorithms for finding and proving optimal solutions for the CVRP compute their lower bounds through column generation and improving it by adding cutting planes. The columns generated may be elementary routes, where customers are visited only once, or relaxations such as q-routes and the more recent ng-routes, which differ on how they allow repeating customers along the routes. Cuts may be classified as robust, those that are defined over arc variables, and non-robust (or strong), those that are defined over the column generation master problem variables. The term robust used above refers to how adding the cut modifies the efficiency of solving the pricing problem. Besides the description above, the most efficient exact algorithms for the CVRP use too many elements turning its replication a hard long task. The objective of this work is to determine how good can be lower bounds computed by a column generation algorithm on ng-routes using only capacity cuts and a family of strong cuts, the limited memory subset row cuts. We assess the leverage achieved with the consideration of this kind of strong cuts and its combination with others techniques like Decremental Space State Relaxation (DSSR), Completion Bounds, ng-Routes and Capacity Cuts over a Set Partitioning formulation of the problem. Extensive computational experiments are presented along with an analysis of the results obtained.

[pt] Neste trabalho apresenta-se a implementação de um sistema de medição de pulsos ópticos curtos gerados por lasers semicondutores. Através de uma técnica indireta de medida, que usa a radiação de segundo harmônico gerada internamente nesses lasers, a duração dos pulsos curtos de luz é estimada. São apresentadas as principais considerações teóricas e experimentais envolvidas com a emissão de segundo harmônico em diodos lasers e são discutidas as principais limitações da técnica. Mostra-se que embora a determinação exata da duração dos pulsos exija medidas adicionais, é possível inferir com boa resolução temporal a duração de pulsos ópticos gerados nos regimes de chaveamento de ganho e mode-locking. / [en] In this work the implementation of a measurement system of short optical pulses generated by semiconductor lasers is presented. This indirect method estimates the pulse duration using the internally generated second harmonic radiation from these lasers. The main theoretical and experimental considerations related with the second harmonic emission are also presented. Although the precise pulse duration requires aditional measurements it is possible to estimate the duration of optical pulses generated by gain-switching and mode-loching regimes with good time-resolution.