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

[pt] Este trabalho propõe um novo modelo linear por partes para a extração de regras de conhecimento de banco de dados. O modelo é uma heurística baseada em análise de árvore de regressão, como introduzido por Friedman (1979) e discutido em detalhe por Breiman (1984). A motivação desta pesquisa é trazer uma nova abordagem combinando técnicas estatísticas de modelagem e um algoritmo de busca por quebras eficiente. A decisão de quebra usada no algoritmo de busca leva em consideração informações do ajuste de equações lineares e foi implementado tendo por inspiração o trabalho de Tsay (1989). Neste, ele sugere um procedimento para construção um modelo para a análise de séries temporais chamado TAR (threshold autoregressive model), introduzido por Tong (1978) e discutido em detalhes por Tong e Lim (1980) e Tong (1983). O modelo TAR é um modelo linear por partes cuja idéia central é alterar os parâmetros do modelo linear autoregressivo de acordo com o valor de uma variável observada, chamada de variável limiar. No trabalho de Tsay, a Identificação do número e localização do potencial limiar era baseada na analise de gráficos. A idéia foi então criar um novo algoritmo todo automatizado. Este processo é um algoritmo que preserva o método de regressão por mínimos quadrados recursivo (MQR) usado no trabalho de Tsay. Esta talvez seja uma das grandes vantagens da metodologia introduzida neste trabalho, visto que Cooper (1998) em seu trabalho de análise de múltiplos regimes afirma não ser possível testar cada quebra. Da combinação da árvore de decisão com a técnica de regressão (MQR), o modelo se tornou o TS-TARX (Tree Structured - Threshold AutoRegression with eXternal variables). O procedimento consiste numa busca em árvore binária calculando a estatística F para a seleção das variáveis e o critério de informação BIC para a seleção dos modelos. Ao final, o algoritmo gera como resposta uma árvore de decisão (por meio de regras) e as equações de regressão estimadas para cada regime da partição. A principal característica deste tipo de resposta é sua fácil interpretação. O trabalho conclui com algumas aplicações em bases de dados padrões encontradas na literatura e outras que auxiliarão o entendimento do processo implementado. / [en] This research work proposes a new piecewise linear model to extract knowledge rules from databases. The model is an heuristic based on analysis of regression trees, introduced by Friedman (1979) and discussed in detail by Breiman (1984). The motivation of this research is to come up with a new approach combining both statistical modeling techniques and an efficient split search algorithm. The split decision used in the split search algorithm counts on information from adjusted linear equation and was implemented inspired by the work of Tsay (1989). In his work, he suggests a model-building procedure for a nonlinear time series model called by TAR (threshold autoregressive model), first proposed by Tong (1978) and discussed in detail by Tong and Lim (1980) and Tong (1983). The TAR model is a piecewise linear model which main idea is to set the coefficients of a linear autoregressive process in accordance with a value of observed variable, called by threshold variable. Tsay`s identification of the number and location of the potential thresholds was based on supplementary graphic devices. The idea is to get the whole process automatic on a new model-building process. This process is an algorithm that preserves the method of regression by recursive least squares (RLS) used in Tsay`s work. This regression method allowed the test of all possibilities of data split. Perhaps that is the main advantage of the methodology introduced in this work, seeing that Cooper, S. (1998) said about the impossibility of testing each break.Thus, combining decision tree methodology with a regression technique (RLS), the model became the TS-TARX (Tree Structured - Threshold AutoRegression with eXternal variables). It searches on a binary tree calculating F statistics for variable selection and the information criteria BIC for model selection. In the end, the algorithm produces as result a decision tree and a regression equation adjusted to each regime of the partition defined by the decision tree. Its major advantage is easy interpretation.This research work concludes with some applications in benchmark databases from literature and others that helps the understanding of the algorithm process.