[pt] Em função da dependência dos regimes hidrológicos, a incerteza associada ao planejamento energético no Brasil exige a modelagem estocástica das Séries Temporais associadas de maneira adequada e coerente. Percebe-se, portanto, a importância dos modelos de geração de cenários hidrológicos com vistas à otimização, via Programação Dinâmica Dual Estocástica (PDDE), do desempenho das operações do sistema elétrico, com consequente aumento de benefícios e confiabilidade e, sobretudo, redução de custos. Esta modelagem estocástica tem sido realizada por um modelo Autorregressivo Peridódico, PAR(p), que ajusta um modelo autorregressivo de ordem p para cada um dos estágios das séries históricas que compõem as configurações do sistema. Este trabalho mostra que a estrutura utilizada no processo de simulação de séries sintéticas do modelo vigente no Setor Elétrico Brasileiro, via distribuição Lognormal, gera uma não linearidade na equação do modelo, o que pode ocasionar inconvenientes de não convexidade que inviabilizam o correto cálculo das Funções de Custo Futuro, poliedros convexos aproximados por funções lineares por partes. Haja vista o exposto e as características do modelo estocástico gerador da árvore de cenários e sua utilização em modelos de otimização, este trabalho apresenta uma nova metodologia alternativa para a construção dos cenários, de forma que os inconvenientes supracitados sejam eliminados. Isto posto, será apresentado uma nova abordagem geral para a construção das árvores, considerando os passos Forward e Backward, fundamentais no processo de otimização empregado pela técnica de PDDE. A estrutura de simulação estocástica desenvolvida conjugou a técnica de computação intensiva de Bootstrap e o método de simulação de Monte Carlo. Foram geradas árvores de cenários com horizonte temporal condizente com o planejamento de médio prazo do despacho hidrotérmico. As séries sintéticas foram comparadas às históricas por meio de uma bateria de testes estatísticos e a aderência das séries geradas foi atestada, provando a adequabilidade do modelo desenvolvido no que tange à parte estocástica do problema. Por fim, a árvore de cenários gerada foi aplicada na PDDE e várias variáveis de resposta foram analisadas, permitindo concluir que o modelo desenvolvido é perfeitamente capaz de reproduzir estruturas compatíveis com o modelo vigente, contudo sem causar a referida não linearidade na equação do PAR(p) e a possível não convexidade do problema de otimização associado ao planejamento de operação de médio/longo prazo. / [en] Due to the highly dependence on the hydrological regimes, the uncertainty associated with energy planning in Brazil requires stochastic modeling of associated time series appropriately and consistently. It is clear, therefore, the importance of models to generate hydrologic scenarios to be used in the optimization via Stochastic Dual Dynamic Programming (SDDP), which improves the performance of system operations, with consequent increase in benefits and reliability and, above all, cost reduction. This stochastic modeling is performed by the PAR(p), which sets an autoregressive model of order p for each of the stages of the historical series that make up the system settings. It was shown in this work that the structure used in the simulation process of synthetic series of the model prevailing in SEB via lognormal distribution generates a nonlinearity relationship in the model equation, which causes the inconvenience of nonconvexity in the calculation of Expected Cost-to-go Functions, convex polyhedral approximated by piecewise linear functions. Considering the above and the characteristics of the stochastic model that generates the scenarios tree and its use in the optimization algorithms, this study aims the development of an alternative methodology for the construction of scenarios, so that the aforementioned drawbacks were eliminated. It is proposed a new general approach for the construction of trees, considering the steps Forward and Backward, fundamental in the process of optimization technique employed by SDDP. The structure of stochastic simulation technique developed conjugates computationally intensive Bootstrap method and Monte Carlo simulation. Scenarios trees were generated consistent with the medium-term planning of hydrothermal dispatch. The synthetic series were compared to the historical data through a battery of statistical tests and the goodness fiting of the series generated was tested that confirmed the suitability of the developed model with respect to the stochastic problem. Finally, the paths of the trees were applied to the SDDP and response variables were analyzed, leading to the conclusion that the model was able to perfectly reproduce structures compatible with the current model, but without causing the aforementioned non-linearity of the PAR(p) equation and possible non convexity in the Expected Cost-to-go Functions.

[pt] Calcular o valor do fluxo máximo entre um nó origem e um nó destino em uma rede é um problema clássico no contexto de Fluxos em Redes. Sua extensão, chamada de problema do fluxo máximo multiterminal, consiste em achar os valores dos fluxos máximos entre todos os pares de nós de uma rede não direcionada. Estes problemas possuem diversas aplicações, especialmente nos campos de transporte, logística, telecomunicações e energia. Neste trabalho, apreciamos a recente teoria da análise de sensibilidade, em que se estuda a influência da variação de capacidade de arestas nos fluxos máximos multiterminais, e estendemos a computação dinâmica dos fluxos multiterminais para o caso de mais de uma aresta com capacidade variável. Através dessa teoria, relacionamos também nós de corte e fluxos multiterminais, o que permitiu desenvolver um método competitivo para solucionar o problema do fluxo máximo multiterminal, quando a rede possui nós de corte. Os resultados dos experimentos computacionais conduzidos com o método proposto são apresentados e comparados com os de um algoritmo clássico, fazendo uso de instâncias geradas e outras conhecidas da literatura. Por último, aplicamos a teoria apresentada em um problema de identificação de complexos de proteínas em redes de interação proteína-proteína. Através da generalização de um algoritmo e de um resultado teórico sobre exclusão de cortes mínimos, foi possível reduzir o número de cálculos de fluxo máximo necessários para identificar tais complexos. / [en] Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.

[pt] Determinar a viabilidade e a prioridade de investimentos potenciais é um passo crítico para a tomada de decisões no âmbito empresarial. O método mais difundido e aceito mundialmente para análise de projetos é o Fluxo de Caixa Descontado (FCD), onde o valor do projeto é determinado pelo Valor Presente Líquido (VPL). No entanto, o FCD não reflete o valor da ação gerencial, maximizadora de resultados, assumindo implicitamente que a firma detém passivamente seus ativos reais (projetos). Sendo este método, portanto, muito limitado para tratar de incertezas e flexibilidades e levando freqüentemente a decisões equivocadas. Considerado por muitos renomados autores um novo paradigma na avaliação de investimentos, a Teoria de Opções Reais (TOR) veio complementar a teoria do FCD, exercendo um papel de ponte entre a intuição estratégica e o rigor analítico. Este trabalho tem por objetivo não somente apresentar algumas das várias flexibilidades existentes em projetos de incorporação imobiliária, como também mostrar como calcular seu valor de forma simples, intuitiva e adequada aos principais problemas de investimento enfrentados por empresas incorporadoras no seu dia a dia. A abordagem de avaliação de investimentos utilizando a TOR possibilita o entendimento das flexibilidades e incertezas inerentes ao processo de incorporação, auxiliando na elaboração de contratos com terceiros e provendo preciosos insights sobre negócios e investimentos estratégicos cada vez mais importantes devido ao acelerado ritmo de mudança econômica. / [en] In an enterprise scope, one critical step in the decision making process is the determination of potential investments feasibility and priority. Worldwide the most accepted method for evaluating a project is the Discounted Cash Flow (DCF), where the value of the project is given by the Net Present Value (NPV). However, the DCF does not reflect the value of managerial action, which maximizes results, assuming implicitly that the firm manages its real assets (projects) passively. Therefore, this method is too limited to deal with uncertainties and flexibilities and often leads to wrong decisions. Considered by many respected authors as a new paradigm in investment valuation, the Real Options Theory is viewed as a complement to standard DCF analysis which bridges the gap between strategic intuition and analytical rigor. This work aims not only to introduce some of the many flexibilities that exist in real estate development projects, but also to show how to evaluate projects in a simple and intuitive manner suitable for the investment decisions that developers face day by day. The Real Options approach provides the understanding of the flexibilities and uncertainties inherent to the project development process, assisting in contract making with third parties, as well as providing precious insights about businesses and strategic investments, insights that are more important than ever given the rapid pace of economic change.

[pt] A avaliação dos projetos de investimentos é uma tarefa difícil para muitas empresas, especialmente para aqueles cujo fluxo de caixa depende dos preços das commodities, já que o nível de incerteza nos preços tem um alto impacto na determinação do momento adequado para o investimento. Os métodos de avaliação tradicionais, que não levam em consideração a flexibilidade gerencial nem a modelagem da incerteza do projeto, podem levar a decisões não ótimas. Esta pesquisa desenvolve um modelo que considera estas variáveis, usando árvores binomiais implícitas ajustados por outros indicadores de risco, como assimetria e curtose da rentabilidade do projeto. O nível de incerteza pode não só ser medido pela volatilidade do retorno do projeto, mas também pela probabilidade de se obter um resultado baixo ou negativo no projeto. A magnitude dessa probabilidade poderia ser a avaliada conhecendo-se o valor da assimetria e curtose do retorno do projeto. Para modelar o comportamento de um projeto, esta dissertação apresenta dois tipos de árvores binomiais implícitas, recombinantes e não recombinante. Cada árvore tem sua própria abordagem específica para determinar o valor do projeto, incluindo opções. Um caso aplicado é apresentado considerando uma empresa de mineração. Os resultados sugerem que o nível de assimetria contribui para uma melhor avaliação do risco do projeto, que combinado com a metodologia de opções reais captura melhor o valor das flexibilidades do projeto; o que é uma importante contribuição do modelo proposto nesta dissertação. / [en] Valuation of capital investment projects is a difficult task for many companies, especially for those whose cash flows depend on commodity prices. The level of uncertainty in commodity prices has a significant impact in determining the proper timing for an investment. Traditional valuation methods, which do not take into account managerial flexibility or project uncertainty modeling can lead to non-optimal decisions. This research develops a dynamic model that considers these variables, and uses implied binomial trees adjusted by other indicators of risk, such as project return s skewness and kurtosis. The level of uncertainty can not only be measured by the project return s volatility, but also by how probable is the occurrence of a low or negative result in the project. The magnitude of this probability could be assessed by knowing the project return s skewness and kurtosis. To model the project s behavior, this dissertation presents two kinds of implied binomial trees, recombining and non-recombining trees. Each tree has its own specific approach to determining the value of the project, including options or managerial flexibility. An applied case is presented considering a mining project. The results suggest that the level of skewness helps to have a better measure of project risk, which combined with the real option approach, allows capturing the value of project managerial flexibilities; which is an important contribution of the proposed model in this dissertation.

[pt] O principal objetivo desta dissertação é estudar modelos de previsão da geração eólica utilizando os dados de cinco parques eólicos, mais precisamente comparar o desempenho dos modelos lineares e não lineares. Utilizando a metodologia do modelo não-linear STAR-TREE (Smooth Transition AutoRegression Tree) e comparando com o modelo linear Box e Jenkins através de medidas estatísticas. Basicamente, o modelo STAR-TREE é uma combinação dos modelos STAR (Smooth Transition AutoRegression) e CART (Classification and Regression Tree), realizando assim uma modelagem em árvore onde a transição entre os regimes é feita de forma suave através da função logística e nos nós terminais são ajustados modelos preditivos. Neste estudo será ajustado nos nós terminais um modelo simples constante e também modelos autorregressivos. / [en] The main objective of this dissertation is to study wind generation forecasting models using data from five wind farms, more accurately compare the performance of linear and nonlinear models. Using the methodology of the nonlinear model STAR-TREE (Smooth Transition Autoregression Tree) and compare with the linear model BoxandJenkins through statistical measures. Basically the model STAR-TREE is a combination of models STAR (Smooth Transition Autoregression) and CART (Classification and Regression Tree), thus creating a modeling tree where the transition between regimes is done smoothly through the logistics function and in the terminal nodes are adjusted predictive models. In this study will fit in the terminal nodes, a simple model of constant and a autoregressive models.

[pt] A metodologia Box & Jenkins tem sido mais utilizada para fazer previsões do que outros métodos até então. Alguns analistas têm relutado, entretanto, em usar esta metodologia, em parte porque a identificação da estrutura adequada é uma tarefa complexa. O reconhecimento tanto dos padrões de comportamento das funções de autocorrelação quanto da autocorrelação parcial (teórica/estimada) dependem da série temporal através da qual é possível extraí-las. Uma vez obtidos os resultados, pode-se inferir qual o tipo de estrutura Box & Jenkins adequada para a série. A proposta do trabalho é desenvolver três novas metodologias de identificação automática das estruturas Box & Jenkins ARMA simples e/ou sazonais, identificar os filtros sazonal e linear da série de uma forma menos complexa. A primeira metodologia utiliza árvores de decisão, a segunda, redes neurais e a terceira, K-Nearest Neighbor (KNN). A estas metodologias serão utilizadas as estruturas Box & Jenkins sazonais de períodos 3, 4, 6 e 12 e não sazonais. Os resultados são aplicados a séries simuladas, bem como a séries reais. Como comparação, utilizou-se o método automático de identificação proposto no software FPW-XE. / [en] The Box & Jenkins is the most popular forecasting technique. However, some researchers have not embraced it because the identification of its structure is highly complex. The process of proper characterizing the properties of both autocorrelation functions and partial correlation (theoretical or estimated) depends on the time series from which they are being obtained. Given the results in question, it is possible to infer the proper Box & Jenkins structure for the time series being studied. For the reasons above, the goal of this dissertation is to develop three new methodologies to identifying, in an automatic fashion, the Box & Jenkins structure of an ARMA series. The methodologies identify, in a simpler manner, both the seasonal and linear filters of the series. The first methodology applies the decision tree. The second applies the neural networks. The third applies the K-Nearest Neighbor (KNN). In each of them the Box & Jenkins seasonal structures of 3, 4, 6 and 12 periods were used, as well as the nonseasonal structure. The results are applied to simulated and actual series. For comparison purposes, the automatic identification procedure of the software FPW-XE is also used.

[pt] Em ambientes dinâmicos, os modelos de dados tendem a ter desempenho insatisfatório uma vez que a distribuição subjacente dos dados muda. Este fenômeno é conhecido como Concept Drift. Em relação a este tema, muito esforço tem sido direcionado ao desenvolvimento de métodos capazes de detectar tais fenômenos com antecedência suficiente para que os modelos possam se adaptar. No entanto, explicar o que levou ao drift e entender suas consequências ao modelo têm sido pouco explorado pela academia. Tais informações podem mudar completamente a forma como adaptamos os modelos. Esta dissertação apresenta uma nova abordagem, chamada Detector de Drift Interpretável, que vai além da identificação de desvios nos dados. Ele aproveita a estrutura das árvores de decisão para prover um entendimento completo de um drift, ou seja, suas principais causas, as regiões afetadas do modelo e sua severidade. / [en] In a dynamic environment, models tend to perform poorly once the underlying distribution shifts. This phenomenon is known as Concept Drift. In the last decade, considerable research effort has been directed towards developing methods capable of detecting such phenomena early enough so that models can adapt. However, not so much consideration is given to explain the drift, and such information can completely change the handling and understanding of the underlying cause. This dissertation presents a novel approach, called Interpretable Drift Detector, that goes beyond identifying drifts in data. It harnesses decision trees’ structure to provide a thorough understanding of a drift, i.e., its principal causes, the affected regions of a tree model, and its severity. Moreover, besides all information it provides, our method also outperforms benchmark drift detection methods in terms of falsepositive rates and true-positive rates across several different datasets available in the literature.

[pt] Mudanças recentes em mercados de energia com alta penetração de fontes renováveis destacaram a necessidade de estratégias complexas que, além de maximizar o lucro, proporcionam proteção contra a volatilidade de preços e incerteza na geração. Neste contexto, este trabalho propõe um modelo dinâmico para representar a tomada de decisão sequencial no cenário atual. Ao contrário de trabalhos relatados anteriormente, este método fornece uma estrutura para considerar as incertezas nos níveis estratégico (longo prazo) e operacional (curto prazo) simultaneamente. É utilizado um modelo de programação estocástica multiestágio em que as correlações entre previsões de vazão, geração renovável, preços spot e preços contratuais são consideradas por meio de uma árvore de decisão multi-escala. Além disso, a aversão ao risco do agente comercializador é considerada por meio de restrições intuitivas e consistentes no tempo. É apresentado um estudo de caso do setor elétrico brasileiro, no qual dados reais foram utilizados para definir a estratégia ótima de comercialização de um gerador de energia eólica, condicionada à evolução futura dos preços de mercado. O modelo fornece ao comercializador informações úteis, como o montante contratado ideal, além do momento ótimo de negociação e duração dos contratos. Além disso, o valor desta solução é demonstrado quando comparado a abordagens estáticas, através de uma medida de desempenho baseada no equivalente de certo do problema multiestágio. / [en] Recent market changes in power systems with high renewable energy penetration highlighted the need for complex profit maximization and protection against price volatility and generation uncertainty. This work proposes a dynamic model to represent sequential decision making in this current scenario. Unlike previously reported works, we contemplate uncertainties in both strategic (long-term) and operational (short-term) levels, all considered as pathdependent stochastic processes. The problem is represented as a multistage stochastic programming model in which the correlations between inflow forecasts, renewable generation, spot and contract prices are accounted for by means of interconnected long- and short-term decision trees. Additionally, risk aversion is considered through intuitive time-consistent constraints. A case study of the Brazilian power sector is presented, in which real data was used to define the optimal trading strategy of a wind power generator, conditioned to the future evolution of market prices. The model provides the trader with useful information such as the optimal contractual amount, settlement timing, and term. Furthermore, the value of this solution is demonstrated when compared to state-of-the-art static approaches using a multistage-based certainty equivalent performance measure.

[pt] Devido ao grande aumento da competitividade e da, cada vez maior, demanda por eficiência, muitas empresas perceberam que é necessário repensar e melhorar seus processos. Para atingir este objetivo, elas têm cada vez mais buscado técnicas computacionais que sejam capazes de extrair novas informações e conhecimentos de suas grandes bases de dados. Os processos das empresas, normalmente, possuem momentos em que uma decisão deve ser tomada. É razoável esperar que casos similares tenham decisões parecidas sendo tomadas ao longo do processo. O objetivo desta dissertação é criar um minerador de decisão que seja capaz the automatizar a tomada de decisão dentro de um processo. A primeira parte do trabalho consiste na identificação dos pontos de decisão em uma rede de Petri. Em seguida, transformamos a tomada de decisão em um problema de classificação no qual cada possibilidade da decisão se torna uma classe. Para fazer a automatização, é utilizada uma árvore de decisão treinada com os atributos dos dados que estão presentes nos logs dos eventos. Um estudo de caso real é utilizado para validar que o minerador de decisão é confiável para processos reais. / [en] Due to the increasing competitiveness and demand for higher performance, many companies realized that it is necessary to rethink and enhance their business processes. In order to achieve this goal, companies have been turning to computational techniques that are capable of extracting new information and insights from their, ever-increasing, datasets. Business processes, normally, have many places where a decision has to be made. It is reasonable to expect that similar inputs have the same decisions made to them during the process. The goal of this dissertation is to create a decision miner that automates the decision-making inside a process. First, we will identify decision points in a Petri net model. Then, we will transform the decision-making problem into a classification one, where each of the possible decisions becomes a class. In order to automate the decision-making, a decision tree is trained using data attributes from the event logs. A real world case study is used to validate that the decision miner is reliable when using real world data.

[pt] Esta tese generaliza a variante multi-período do clássico problema da Árvore de Steiner com coleta de prêmios (PCST), que visa encontrar um subgrafo conexo que maximize os prêmios recuperados de nós conectados menos o custo de utilização das arestas conectadas. Este trabalho adicionalmente: (a) permite que vértices sejam conectados à árvore em diferentes períodos de tempo; (b) impõe um orçamento pré-definido em arestas selecionadas em um horizonte específico de períodos de tempo; e (c) limita o comprimento total de arestas que podem ser adicionadas em um período de tempo. Um algoritmo branch-and-cut é fornecido para este problema, avaliando satisfatoriamente instâncias benchmark da literatura, adaptadas para uma configuração multi-período, de até aproximadamente 2000 vértices e 200 terminais em tempo razoável. / [en] This thesis generalizes the multi-period variant of the classical Prizecollecting Steiner Tree Problem, which aims at finding a connected subgraph that maximizes the revenues collected from connected nodes minus the costs to utilize the connecting edges. This work additionally: (a) allows vertices to be added to the tree at different time periods; (b) imposes a predefined budget on edges selected over a specific horizon of time periods; and (c) limits the total length of edges that can be added over a time period. A branch-and-cut algorithm is provided for this problem, satisfactorily evaluating benchmark instances from the literature, adapted to a multi-period setting, up to approximately 2000 vertices and 200 terminals in reasonable time.