[pt] A parte mais difícil de modelar os problemas de tomada de decisão do mundo real, é a incerteza associada a realização de eventos futuros. A programação estocástica se encarrega desse assunto; o objetivo é achar soluções que sejam factíveis para todas as possíveis realizações dos dados, otimizando o valor esperado de algumas funções das variáveis de decisão e de incerteza. A abordagem mais estudada está baseada em simulação de Monte Carlo e o método SAA (Sample Average Appmwimation) o qual é uma formulação do problema verdadeiro para cada realização da data incerta, que pertence a um conjunto finito de cenários uniformemente distribuídos. É possível provar que o valor ótimo e a solução ótima do problema SAA converge a seus homólogos do problema verdadeiro quando o número de cenários é suficientemente grande.Embora essa abordagem seja útil ali existem fatores limitantes sobre o custo computacional para obter soluções mais precisas aumentando o número de cenários; no entanto o fato mais importante é que o problema SAA é função de cada amostra gerada e por essa razão é aleatório, o qual significa que a sua solução também é incerta, e para medir essa incerteza e necessário considerar o número de replicações do problema SAA afim de estimar a dispersão da solução, aumentando assim o custo computacional. O propósito deste trabalho é apresentar uma abordagem alternativa baseada em um método de partição que permite obter cotas para estimar deterministicamente a solução do problema original, com aplicação da desigualdade de Jensen e de técnicas de otimização robusta. No final se analisa a convergência dos algoritmos de solução propostos. / [en] The hardest part of modelling decision-making problems in the real world, is the uncertainty associated to realizations of futures events. The stochastic programming is responsible about this subject; the target is finding solutions that are feasible for all possible realizations of the unknown data, optimizing the expected value of some functions of decision variables and random variables. The approach most studied is based on Monte Carlo simulation and the Sample Average Approximation (SAA) method which is a kind of discretization of expected value, considering a finite set of realizations or scenarios uniformly distributed. It is possible to prove that the optimal value and the optimal solution of the SAA problem converge to their counterparts of the true problem when the number of scenarios is sufficiently big. Although that approach is useful, there exist limiting factors about the computational cost to increase the scenarios number to obtain a better solution; but the most important fact is that SAA problem is function of each sample generated, and for that reason is random, which means that the solution is also uncertain, and to measure its uncertainty it is necessary consider the replications of SAA problem to estimate the dispersion of the estimated solution, increasing even more the computational cost. The purpose of this work is presenting an alternative approach based on robust optimization techniques and applications of Jensen s inequality, to obtain bounds for the optimal solution, partitioning the support of distribution (without scenarios creation) of unknown data, and taking advantage of the convexity. At the end of this work the convergence of the bounding problem and the proposed solution algorithms are analyzed.

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

[pt] Os sistemas rodoviários são grandes candidatos à aplicação de técnicas de otimização para a redução dos custos operacionais. Neste trabalho são apresentados dois modelos de programação inteira para problemas nesta área, o Problema de Transferência de Cargas (PTC) e o Problema de Alocação de Cargas (PAC). Ambos foram resolvidos de maneira ótima ou quase ótima em tempo razoável, tanto em termos acadêmicos como para sua utilização prática. São apresentados os problemas, as formulações dos modelos, as técnicas de pré-processamento utilizadas, assim como resultados computacionais de instâncias reais. / [en] Road systems are major candidates for the use of optimization techniques to obtain operational reduction costs. In this research we present two integer programming models for road problems, the Load Transference Problem and the Load Scheduling Problem. Both problems were solved to optimality or near-optimality in a reasonable time, either for academic or practical purposes. We present the descriptions of the problems, the mathematical formulations, the preprocessing techniques used, as well as computational results for real instances.

[pt] O desenvolvimento da indústria de Gás Natural pelo mundo resultou em um processo de integração entre os setores de gás natural e eletricidade em diversos países. Entretanto, em alguns casos, como o Brasil, apesar de a demanda de gás para uso convencional (industrial, comercial, residencial, GNV) ter crescido a taxas relativamente altas, ela sozinha ainda não justifica novos grandes investimentos na produção e no transporte de gás. Verifica-se que, neste caso, o setor de energia desempenha um papel indispensável por se tratar do maior mercado potencial de gás natural, com a escala suficiente para ser a âncora de demanda que viabiliza os investimentos em produção e transporte do gás. Todavia, devido à predominância hidrológica no sistema elétrico Brasileiro, o despacho das térmicas é bastante volátil e, por conseqüência, o consumo de gás das térmicas é bastante variável. Assim, o produtor de gás está sujeito a um fluxo de caixa muito volátil e incerto e cláusulas de compra compulsória de gás (takeor-pay) e de remuneração do custo da infra-estrutura (ship-or-pay) são observadas. Enquanto estas cláusulas trazem certeza necessária para viabilizar a produção, elas oneram excessivamente os custos das Usinas Térmicas, que se vêem obrigadas a pagar pelo combustível e, portanto, gerar, mesmo quando o preço da energia esteja inferior ao seu custo marginal de produção. Tendo em vista este cenário, foi recentemente discutida no âmbito do Governo Federal a criação de um mercado flexível de gás natural, onde contratos interruptiveis de gás (lastreados no take-or-pay das térmicas) seriam fornecidos a consumidores industriais. Nestes contratos, o fornecimento seria interrompido se a Usina Térmica fosse despachada. O objetivo desta tese é analisar a criação deste mercado sob a ótica dos consumidores. Será verificada a disposição a pagar por um contrato interruptível de gás levando em consideração a incerteza associada ao suprimento (que depende da prioridade de uso do gás pelas térmicas) e o perfil de risco destes consumidores. / [en] With the development of the gas industry worldwide, a process of strengthening the integration between the natural gas and the electricity sectors is underway in several countries. However, although gas demand has been growing at relatively high rates, this demand growth solely is unlikely to justify new large investments in gas production and transportation. This means that the power sector ends up being the largest potential market for natural gas, with the needed scale to provide the necessary anchor demand to spur these production and infrastructure investments. The hydro predominance in the country creates volatility on the dispatch of the gas-fired plants, which ends up creating an undesirable (from the gas-sector point of view) volatility in the natural gas consumption. Since the gas-market is still incipient, gas contracts are typically of long-term with high take or pay and ship or pay clauses to ensure financing of the production- transportation infrastructure. From the power sector point of view, these clauses are undesirable: due to the uncertainty of dispatch gas-based generators want to negotiate a higher flexibility. As such, the aim of this work is to determine the impacts due to the creation of a flexible (secondary) gas market from the costumers´ point of view. It will be also developed the costumers´ willto- contract curve, which will take into account the uncertainty of thermoelectric dispatch (that rules the gas availability over this new proposed market) and the risk-profile of costumers.

[pt] O sistema elétrico brasileiro apresenta características especiais que fazem com que ele se torne diferente dos outros encontrados nos demais países do mundo. Um território de largas dimensões abriga diversas bacias hidrográficas, as quais muitas vezes apresentam comportamentos complementares exigindo um grande intercâmbio energético entre elas, o que ocasionou a construção de uma malha de transmissão de grande porte e muito interligada. Com isto tornou-se necessária a construção de modelos específicos para gerenciar a operação elétrica e energética de todos os componentes do sistema distribuídos ao longo do país. O problema do planejamento da operação de sistemas elétricos é divido em diversas etapas separadas de acordo com o horizonte de estudo, do médio prazo até o despacho horário. Em cada etapa a representação da aleatoriedade das afluências às usinas hidrelétricas e o detalhamento do sistema elétrico é diferente. No planejamento de médio prazo é importante analisar o impacto das secas de longa duração na operação do sistema, a sua probabilidade de ocorrência e a capacidade de regularização plurianual do sistema brasileiro. Nesta fase as usinas hidrelétricas são representadas de forma simplificada através de sistemas equivalentes e existe uma representação detalhada da estocasticidade das afluências através da análise de diversos cenários hidrológicos. Na medida em que o horizonte de estudo diminui, a incerteza sobre as afluências futuras também diminui, porém aumenta a necessidade de uma representação mais detalhada das usinas hidrelétricas, térmicas, recebimentos, pequenas centrais hidrelétricas (PCHs) e rede de transmissão. Este trabalho concentra-se nos modelos de médio prazo que radicionalmente utilizam uma representação por sistemas equivalentes. O objetivo é permitir uma representação híbrida, onde parte do sistema será representado através de reservatórios equivalentes de energia e outra, representada à usinas individualizas o que possibilita um maior detalhamento dos estudos de médio prazo. O acoplamento hidráulico existente entre sistemas equivalentes é revisto e o acoplamento hidráulico de sistemas equivalentes com sistemas à usinas individualizadas originado pela representação híbrida é tratado com detalhe. / [en] The Brazilian electric system presents special characteristics which differs from those in other countries. A huge territory which contains several hydrographical basins with frequently complementary behaviors that demand great energy exchanges around all the geographical areas of the country. This has required the construction of a massive transmission network that is hardly interlinked. For this reason it has been necessary to construct specific models to generate the electric and energy operation for all the system`s components dispersed throughout the country. The operation planning of electrical systems problem is separated into several stages, in accord with the study outline, over a long term until the actual operational programming. At each stage the representational of hydraulic plant inflows and the peculiarities of the electric system are different. In the case of long-term planning it is important to analyze the impact of the long lasting droughts, their probability of occurrence and the multi-year reservoir regulation capacity for the Brazilian system. In this phase, hydroelectric plants are represented in a simplified manner and there are a detailed inflows representation. As the study horizon diminishes, the uncertainty about the future inflows also decreases, therefore increasing the need for a more detailed representation of the hydraulic and thermal plants, small hydraulic plants, interchanges and transmission network. This work concentrates on the long-term models which traditionally employ a representation using equivalen. We create here the possibility of a hybrid representation, where part of the hydraulic plants will be represented by equivalent reservoirs and part will be individually represented by total hydraulic coupling throughout all the systems components.

[pt] Impulsionadas pelo crescimento do mercado corporativo e pela prestação de serviços para grandes clientes, as operadoras de serviços de telecomunicação estão buscando processos automatizados e redução de custo no desenvolvimento de novos projetos de redes de telecomunicações. Nesse cenário, dois modelos de Programação Inteira são apresentados buscando uma minimização de custos. O primeiro para o problema de planejamento de novas redes. E segundo para o problema de configuração de trails nas redes SDH. Uma introdução sobre meios de transmissão, redes de telecomunicações, topologias mais utilizadas e sistemas de proteção são apresentados. Por fim, em ambos problemas, são apresentados estudos comparativos com situações reais, com o intuito de validar os modelos. / [en] Stimulated by the growth of the corporate market and by the services dedicated to big customers, providers are searching for, even more nowadays, automated process and cost reduction on the development of new telecommunications networks projects. In that setting, two models of Integer Programming will be presented, seeking a minimization of costs. At first, for the problem of planning of new networks, and second for the problem of configuration of trails in the SDH networks. Beyond that, an introduction about transmission lines, networks of communication, topology more utilized and systems of protection will be presented. In both problems, comparing real situations, with the purpose of validate the models.

[pt] Em vários problemas de distribuição e logística, os produtos devem ser coletados em uma origem e entregues em um destino. Exemplos incluem o transporte de pessoas com deficiência, serviços de correio expresso, logística de suprimentos médicos, etc. O problema de roteamento abordado neste trabalho, conhecido como Traveling Salesman Problem with Pickup and Delivery (TSPPD), é da classe de problemas do caixeiro viajante com restrições de precedência. Neste problema, existe um mapeamento um-para-um entre coleta-entrega no qual cada cliente do tipo coleta possui um cliente do tipo entrega associado. Os clientes do tipo entrega somente podem ser visitados posteriormente à coleta associada. O TSPPD é um problema NP-difícil uma vez que generaliza o Traveling Salesman Problem (TSP). O TSP pode ser visto como um caso particular do TSPPD onde cada coleta coincide espacialmente com a respectiva entrega. As variantes com restrições de capacidade, janelas de tempo e diferentes políticas de carregamento têm recebido maior atenção na última década, embora ainda existam significantes avanços a serem realizados em termos de qualidades de soluções na versão básica do problema. Para resolver este problema, propomos um algoritmo meta-heurístico híbrido com vizinhanças largas exploradas eficientemente em O(n2). Nossos experimentos demonstram uma redução significativa no tempo computacional e também melhoria na qualidade de soluções previamente conhecidas na literatura. / [en] In various distribution and logistics issues, products must be collected at one source and delivered to a destination. Examples include disabled people transportation, express mail services, medical supplies logistics, etc. The routing problem addressed by this work, known as Traveling Salesman Problem with Pickup and Delivery (TSPPD), belongs to the class of traveling salesman problems with precedence constraints. In this problem, there is a one-to-one pickup-delivery mapping in which, for each pickuptype client, there is exactly one associated delivery-type client. Delivery clients can only be visited after the associated pickup. Since the TSPPD generalizes the TSP it is also a NP-hard problem, as the TSP is a particular casa of TSPPD where each pickup matches spatially with it s respective delivery. Variants with capacity constraints, time windows and different loading policies have received more attention in the last decade, although there are still significant advances to be made in terms of solution quality for the basic version of the problem. To solve this problem, we propose a hybrid metaheuristic algorithm with large neighborhoods efficiently explored in O(n2). Our experiments demonstrate a significant computational time reduction and also solutions quality improvement compared to the previous works.

[pt] Programar redes de sensores sem fio (RSSF) é uma tarefa difícil. O programador tem que lidar com várias atividades simultâneas em um ambiente com recursos extremamente limitados. Neste trabalho propomos um modelo de programação para facilitar essa tarefa. O modelo que propomos combina o uso de máquinas virtuais configuráveis baseadas em componentes com uma linguagem de script reativa que pode ser analisada estaticamente para evitar conitos de memória e execução de laços infinitos. Essa abordagem permite a exibilidade de carregamento remoto de código nos nós da rede combinado com um conjunto de garantias para o programador. A escolha de um conjunto específico de componentes numa configuração de máquina virtual define o nível de abstração visto pelo script da aplicação. Para avaliar esse modelo, construímos Terra, um sistema que combina a linguagem de script Céu-T com uma máquina virtual e uma biblioteca de componentes. Nós projetamos esta biblioteca considerando as funcionalidades comumente necessárias em aplicações de RSSF - tipicamente para sensoreamento e controle. Implementamos diferentes aplicações utilizando Terra e uma linguagem orientada a eventos baseados em C. Além disso discutimos as vantagens e desvantagens dessas implementações alternativas. Finalmente, também avaliamos Terra medindo o custo adicional em uma aplicação básica e discutimos sua utilização e custo em diferentes cenários de aplicações WSNs. / [en] Programming wireless sensors networks (WSN) is a difficult task. The programmer must deal with several concurrent activities in an environment with severely limited resources. In this work we propose a programming model to facilitate this task. The model we propose combines the use of configurable component-based virtual machines with a reactive scripting language which can be statically analyzed to avoid unbounded execution and memory conicts. This approach allows the exibility of remotely uploading code on motes to be combined with a set of guarantees for the programmer. The choice of the specific set of components in a virtual machine configuration defines the abstraction level seen by the application script. To evaluate this model, we built Terra, a system combining the scripting language Céu-T with the Terra virtual machine and a library of components. We designed this library taking into account the functionalities commonly needed in WSN applications - typically for sense and control. We implemented different applications using Terra and using an event-driven language based on C and we discuss the advantages and disadvantages of the alternative implementations. Finally, we also evaluate Terra by measuring its overhead in a basic application and discussing its use and cost in different WSN scenarios.

[pt] A alocação de ativos é uma das mais importantes decisões financeiras para investidores. No entanto, as decisões humanas não são totalmente racionais. Sabemos que as pessoas cometem muitos erros sistemáticos como, excesso de confiança, aversão à perda irracional e mau uso da informação entre outros. Nesta tese desenvolvemos duas metodologias distintas para enfrentar esse problema. A primeira abordagem é qualitativa, utiliza o modelo de Black-Litterman e tenta mapear a visão que o investidor tem do mercado. Esse método tenta mitigar a irracionalidade na tomada de decisão tornando mais fácil para um investidor demonstrar suas preferências em relação aos ativos. Black e Litterman desenvolveram um método para otimização de carteiras com a proposta de melhorar o modelo Markowitz, utilizando a construção de visões para representar a opinião do investidor sobre o futuro. No entanto, a forma de construir essas visões é bastante confusa e exige que o investidor estime vários parâmetros que são subjetivos. Assim, propomos uma nova forma de criar essas visões, utilizando Análise Verbal de Decisão. A segunda pesquisa envolve métodos quantitativos para resolver o problema de alocação de ativos com múltiplos estágios com premissas mais realistas. Embora a Programação Dinâmica Dual Estocástica (PDDE) seja uma técnica promissora para a solução de problemas de grande porte, não é adequada para o problema de alocação de ativos devido à dependência temporal associada aos retornos dos ativos. PDDE assume que o processo estocástico tem independência por estágio assegurando uma função única de custo futuro para cada estágio. No problema de alocação de ativos, a dependência do tempo é tipicamente não-linear e no lado esquerdo, o que torna PDDE tradicional não aplicável. Propomos uma variação do PDDE usando modelo oculto de Markov com estados discretos para resolver problemas reais de alocação de ativos com múltiplos períodos e dependência no tempo. Ambas as abordagens foram testadas em dados reais e empiricamente analisadas. As principais contribuições são as metodologia desenvolvidas para simplificar a construção de portfólios e para resolver o problema de alocação de ativos com múltiplos estágios. / [en] Asset allocation is one of the most important financial decisions made by investors. However, human decisions are not fully rational, and people make several systematic mistakes due to overconfidence, irrational loss aversion and misuse of information, among others. In this thesis, we developed two distinct methodologies to tackle this problem. The first approach has a more qualitative view, trying to map the investor s vision of the market. It tries to mitigate irrationality in decision-making by making it easier for an investor to demonstrate his/her preferences for specirfic assets. This first research uses the Black-Litterman model to construct portfolios. Black and Litterman developed a method for portfolio optimization as an improvement over the Markowitz model. They suggested the construction of views to represent an investor s opinion about future stocks returns. However, constructing these views has proven difficult, as it requires the investor to quantify several subjective parameters. This work investigates a new way of creating these views by using Verbal Decision Analysis. The second research focuses on quantitative methods to solve the multistage asset allocation problem. More specifically, it modifies the Stochastic Dynamic Dual Programming (SDDP) method to consider real asset allocation models. Although SDDP is a consolidated solution technique for large-scale problems, it is not suitable for asset allocation problems due to the temporal dependence of returns. Indeed, SDDP assumes a stagewise independence of the random process assuring a unique cost-to-go function for each time stage. For the asset allocation problem, time dependency is typically nonlinear and on the left-hand side, which makes traditional SDDP inapplicable. This thesis proposes an SDDP variation to solve real asset allocation problems for multiple periods, by modeling time dependence as a Hidden Markov Model with concealed discrete states. Both approaches were tested in real data and empirically analyzed. The contributions of this thesis are the methodology to simplify portfolio construction and the methods to solve real multistage stochastic asset allocation problems.

[pt] Modelagem e renderização baseadas em imagem tem sido uma área de pesquisa muito ativa nas últimas décadas, tendo recebido grande atenção como uma alternativa às técnicas tradicionais de síntese de imagens baseadas primariamente em geometria. Nesta área, algoritmos de visão computacional são usados para processar e interpretar fotos ou vídeos do mundo real a fim de construir um modelo representativo de uma cena, ao passo que técnicas de computação gráfica são usadas para tomar proveito desta representação e criar cenas foto-realistas. O propósito deste trabalho é investigar técnicas de renderização capazes de gerar vistas virtuais de alta qualidade de uma cena, em tempo real. Para garantir a performance interativa do algoritmo, além de aplicar otimizações a métodos de renderização existentes, fazemos uso intenso da GPU para o processamento de geometria e das imagens para gerar as imagens finais. Apesar do foco deste trabalho ser a renderização, sem reconstruir o mapa de profundidade a partir das fotos, ele implicitamente contorna possíveis problemas na estimativa da profundidade para que as cenas virtuais geradas apresentem um nível aceitável de realismo. Testes com dados públicos são apresentados para validar o método proposto e para ilustrar deficiências dos métodos de renderização baseados em imagem em geral. / [en] Image-based modeling and rendering has been a very active research topic as a powerful alternative to traditional geometry-based techniques for image synthesis. In this area, computer vision algorithms are used to process and interpret real-world photos or videos in order to build a model of a scene, while computer graphics techniques use this model to create photorealistic images based on the captured photographs or videos. The purpose of this work is to investigate rendering techniques capable of delivering visually accurate virtual views of a scene in real-time. Even though this work is mainly focused on the rendering task, without the reconstruction of the depth map, it implicitly overcomes common errors in depth estimation, yielding virtual views with an acceptable level of realism. Tests with publicly available datasets are also presented to validate our framework and to illustrate some limitations in the IBR general approach.