Orientador: Rubén Augusto Romero Lázaro / Resumo: A grande maioria dos sistemas de distribuição de energia elétrica opera de forma radial. Isso significa que cada carga é alimentada por apenas uma subestação por meio de um único caminho. Entretanto, as redes de distribuição apresentam estrutura malhada, de forma que, caso uma contingência ocorra, o restabelecimento do fornecimento possa ser realizado para o maior número possível de consumidores. Os trabalhos que lidam com o problema de planejamento da expansão de sistemas de distribuição, no entanto, geralmente consideram a expansão do sistema para apenas uma topologia radial, sem levar em conta aspectos da restauração do fornecimento para melhoria dos índices de confiabilidade. Nesse contexto, este trabalho aborda o planejamento de sistemas de distribuição considerando aspectos econômicos e de confiabilidade, de forma a incluir a restauração do fornecimento no problema de planejamento da expansão. Na formulação do problema considera-se a expansão de novas subestações, o reforço de subestações existentes, a construção de novos alimentadores em novos caminhos, a troca de condutores existentes e a alocação de geradores distribuídos, além de expansão multiestágio e restauração do fornecimento para melhoria dos índices de confiabilidade. Dois métodos alternativos são propostos para resolver o problema descrito: o primeiro considera modelos matemáticos com diversos graus de precisão, para serem resolvidos por métodos exatos, e o segundo é uma meta-heurística de busca e vizinhança... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The vast majority of electricity distribution systems are operated radially. This means that each load is supplied by only one substation through a single path. However, distribution networks have a meshed structure so that, in the case of a contingency, the supply is restored to as many customers as possible. The works that deal with the distribution systems expansion planning problem, however, generally consider the expansion of the system for only one radial topology, disregarding the restoration aspects to improve reliability indices. In this context, this work deals with the planning of distribution systems considering economic and reliability aspects, to include the service restoration in the planning problem. In the formulation of the problem, it is considered the expansion of new substations, the reinforcement of existing substations, the construction of new feeders in new paths, the exchange of existing conductors, and the allocation of distribution generation, besides multistage expansion and service restoration to improve the reliability indices of the system. Two alternative methods are proposed to solve the described problem: the first one considers relaxed or approximated mathematical models to be solved by exact methods, and the second one is a variable neighborhood search metaheuristic, which solves the complete model for the problem approximately, without guarantee of optimality. The initial solution of the metaheuristic is generated by a strategy that constr... (Complete abstract click electronic access below) / Doutor

Orientador: Ariovaldo Verandio Garcia, Ruben Augusto Romero Lazaro / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T06:56:43Z (GMT). No. of bitstreams: 1 RiderFlores_MarcosJulio_D.pdf: 1021887 bytes, checksum: 6000961c2f5457b410ac691912476270 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho são propostos modelos matemáticos e técnicas de solução para resolver o problema de planejamento da expansão de sistemas de transmissão através de três enfoques. a) Usando o modelo de corrente alternada do sistema de transmissão e um algoritmo heurístico construtivo especializado para resolver o problema de planejamento, e, ainda, realiza-se uma primeira tentativa de alocação de fontes de potência reativas; b) Usando o modelo de corrente contínua e técnicas de programação não-linear especializadas. Nesse caso emprega-se uma versão relaxada do problema de planejamento da expansão de sistemas de transmissão usando o modelo de corrente contínua, onde a integralidade das variáveis de investimento é desprezada. Resolve-se o problema de programação não-linear, modelado de forma matricial com um algoritmo de otimização especializado e, além disso, um algoritmo heurístico construtivo especializado é utilizado para resolver o problema de planejamento. c) Usando o modelo de corrente contínua e um algoritmo Branch and Bound (B&B) sem empregar técnicas de decomposição. Para isso foram redefinidos os chamados testes de sondagem no algoritmo B&B e em cada nó da árvore de B&B tem-se um problema de programação não-linear que são resolvidos usando a metodologia desenvolvida no item (b). Os ítens (a), (b) e (c) requerem a solução de problemas de programação não-linear diferenciados. Uma revisão das características principais da resolução iterativa dos métodos de pontos interiores é apresentada. Foi desenvolvida uma técnica baseada em uma combinação de métodos de pontos interiores de alta ordem (MPI-AO) para resolver os problemas de programação não-linear de forma rápida, eficiente e robusta. Essa combinação dos MPI-AO tem como objetivo colocar num único método as características particulares de cada um dos MPI-AO e melhorar o desempenho computacional comparado com os MPI-AO de forma individual / Abstract: In this work mathematical models and solution techniques are proposed to solve the power system transmission expansion planning problem through three approaches: a) Using the nonlinear model ofthe transmission system (AC model) and a specialized constructive heuristic algorithm to solve the problem and, yet, a first attempt to allocate reactive power sources is also considered; b) Using the direct-current (DC) model and specialized techniques of nonlinear programming. In this case a version of the power system transmission expansion planning problem using the DC model where the integrality of the investment variables is relaxed is used. The nonlinear programming problem is solved with a specialized optimization algorithm and, moreover, a constructive heuristic algorithm is employed to solve the planning problem. c) Using the DC model and Branch and Bound (B&B) algorithm without the use of decomposition techniques. The so called fathoming tests of the B&B were redefined and at each node of the tree a nonlinear programming problem is solved using the method developed in b). Items a), b) and c) require the solution of distinct problems of nonlinear programming. A revision of the main characteristics of the iterative solution of the interior points methods is presented. An optimization technique based on a combination of the higher order interior point methods (HO-IPM) had been developed to solve the nonlinear programming problems in a fast, efficient and robust way. This combination of the HO-IPM has as objective to explore the particular characteristics of each method in a single one and to improve the comparative computational performance with the HO-IPM of individual form / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

L'objectif de cette thèse consiste à présenter un nouvel algorithme pour la programmation non linéaire en nombres entiers, inspirée par la méthode Multiplicative Weights Update et qui compte sur une nouvelle classe de reformulations, appelées les reformulations ponctuelles.La programmation non linéaire en nombres entiers est un sujet très difficile et fascinant dans le domaine de l'optimisation mathématique à la fois d'un point de vue théorique et computationnel. Il est possible de formuler de nombreux problèmes dans ce schéma général et, habituellement, ils posent de réels défis en termes d'efficacité et de précision de la solution obtenue quant aux procédures de résolution.La thèse est divisée en trois parties principales : une introduction composée par le Chapitre 1, une définition théorique du nouvel algorithme dans le Chapitre 2 et l'application de cette nouvelle méthodologie à deux problèmes concrets d'optimisation, tels que la sélection optimale du portefeuille avec le critère moyenne-variance dans le Chapitre 3 et le problème du sac à dos non linéaire dans le Chapitre 4. Conclusions et questions ouvertes sont présentées dans le Chapitre 5. / This thesis presents a new algorithm for Mixed Integer NonLinear Programming, inspired by the Multiplicative Weights Update framework and relying on a new class of reformulations, called the pointwise reformulations.Mixed Integer NonLinear Programming is a hard and fascinating topic in Mathematical Optimization both from a theoretical and a computational viewpoint. Many real-word problems can be cast this general scheme and, usually, are quite challenging in terms of efficiency and solution accuracy with respect to the solving procedures.The thesis is divided in three main parts: a foreword consisting in Chapter 1, a theoretical foundation of the new algorithm in Chapter 2, and the application of this new methodology to two real-world optimization problems, namely the Mean-Variance Portfolio Selection in Chapter 3, and the Multiple NonLinear Separable Knapsack Problem in Chapter 4. Conclusions and open questions are drawn in Chapter 5.

This thesis examines the optimal scheduling of a hydroelectric power plant with cascaded reservoirs each with multiple generating units under uncertainty after testing three linearization methods. These linearization methods are Successive Linear Programming, Piecewise Linear Approximations, and a Hybrid of the two together. There are two goals of this work. The first goal of this work aims to replace the nonconvex mixed-integer nonlinear program (MINLP) with a computationally efficient linearized mixed-integer linear program (MILP) that will be capable of finding a high quality solution, preferably the global optimum. The second goal is to implement a stochastic approach on the linearized method in a pseudo-rolling horizon method which keeps the ending time step fixed. Overall, the Hybrid method proved to be a viable replacement and performs well in the pseudo-rolling horizon tests. / Thesis / Master of Applied Science (MASc)

Diese Arbeit leistet Beiträge zu zwei Gebieten der mathematischen Programmierung: stochastische Optimierung und gemischt-ganzzahlige nichtlineare Optimierung (MINLP). Im ersten Teil erweitern wir quantitative Stetigkeitsresultate für zweistufige stochastische gemischt-ganzzahlige lineare Programme auf Situationen in denen Unsicherheit gleichzeitig in den Kosten und der rechten Seite auftritt, geben eine ausführliche Übersicht zu Dekompositionsverfahren für zwei- und mehrstufige stochastische lineare und gemischt-ganzzahlig lineare Programme, und diskutieren Erweiterungen und Kombinationen des Nested Benders Dekompositionsverfahrens und des Nested Column Generationsverfahrens für mehrstufige stochastische lineare Programme die es erlauben die Vorteile sogenannter rekombinierender Szenariobäume auszunutzen. Als eine Anwendung dieses Verfahrens betrachten wir die optimale Zeit- und Investitionsplanung für ein regionales Energiesystem unter Einbeziehung von Windenergie und Energiespeichern. Im zweiten Teil geben wir eine ausführliche Übersicht zum Stand der Technik bzgl. Algorithmen und Lösern für MINLPs und zeigen dass einige dieser Algorithmen innerhalb des constraint integer programming Softwaresystems SCIP angewendet werden können. Letzteres erlaubt uns die Verwendung schon existierender Technologien für gemischt-ganzzahlige linear Programme und constraint Programme für den linearen und diskreten Teil des Problems. Folglich konzentrieren wir uns hauptsächlich auf die Behandlung der konvexen und nichtkonvexen nichtlinearen Nebenbedingungen mittels Variablenschrankenpropagierung, äußerer Approximation und Reformulierung. In einer ausführlichen numerischen Studie untersuchen wir die Leistung unseres Ansatzes anhand von Anwendungen aus der Tagebauplanung und des Aufbaus eines Wasserverteilungssystems und mittels verschiedener Vergleichstests. Die Ergebnisse zeigen, dass SCIP ein konkurrenzfähiger Löser für MINLPs geworden ist. / This thesis contributes to two topics in mathematical programming: stochastic optimization and mixed-integer nonlinear programming (MINLP). In the first part, we extend quantitative continuity results for two-stage stochastic mixed-integer linear programs to include situations with simultaneous uncertainty in costs and right-hand side, give an extended review on decomposition algorithm for two- and multistage stochastic linear and mixed-integer linear programs, and discuss extensions and combinations of the Nested Benders Decomposition and Nested Column Generation methods for multistage stochastic linear programs to exploit the advantages of so-called recombining scenario trees. As an application of the latter, we consider the optimal scheduling and investment planning for a regional energy system including wind power and energy storages. In the second part, we give a comprehensive overview about the state-of-the-art in algorithms and solver technology for MINLPs and show that some of these algorithm can be applied within the constraint integer programming framework SCIP. The availability of the latter allows us to utilize the power of already existing mixed integer linear and constraint programming technologies to handle the linear and discrete parts of the problem. Thus, we focus mainly on the domain propagation, outer-approximation, and reformulation techniques to handle convex and nonconvex nonlinear constraints. In an extensive computational study, we investigate the performance of our approach on applications from open pit mine production scheduling and water distribution network design and on various benchmarks sets. The results show that SCIP has become a competitive solver for MINLPs.

Orientador: Rubén Augusto Romero Lázaro / Banca: Jose Roberto Sanches Mantovani / Banca: Anna Diva Plasencia Lotufo / Banca: Marcos Julio Rider Flores / Banca: Eduardo Nobuhiro Asada / Resumo: Nessa pesquisa tem-se por objetivo a análise teórica e a implementação computacional de duas propostas de solução ao problema de planejamento da expansão de sistemas de transmissão de energia elétrica considerando diferentes fatores relacionados com a confiabilidade do sistema e a adoção dos novos modelos de mercados elétricos. É importante notar, que no planejamento básico não são levados em conta esses importantes aspectos. Dessa forma, uma primeira aproximação considera um critério de confiabilidade para expandir o sistema, de forma que ele opere adequadamente no horizonte de planejamento satisfazendo um nível de confiabilidade pré-definido. O índice de confiabilidade utilizado para exigir esse nível de confiabilidade é o LOLE, que corresponde ao número médio de horas/dias em um período dado (normalmente um ano) no qual o pico da carga horária/diária do sistema possivelmente exceder'a a capacidade de geração disponível. O problema de planejamento considerando a confiabilidade é, portanto, formulado como um problema de otimização que minimiza o investimento sujeito ao critério de confiabilidade. O índice de confiabilidade para o sistema de transmissão é calculado para cada configuração, subtraindo o índice de confiabilidade do sistema de geração do sistema composto geração-transmissão (bulk power system ). Para calcular o índice no sistema composto geração transmissão, utiliza-se uma curva de duração de carga efetiva para este sistema. Esta curva acumulada de carga é obtida de um processo de convolução de outras duas curvas que representam a função de distribuição de probabilidade (FDP) das saídas aleatórias dos componentes do sistema e a curva de duração de carga, respectivamente. A avaliação de confiabilidade no sistema de geração é feita usando um método que calcula o índice de confiabilidade por meio dos momentos... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work aims to the theoretical analysis and computational implementation of two proposals for the transmission expansion planning problem considering several factors such as system reliability and new electricity market structures. It is important to observe, that the basic planning does not consider these issues. Therefore, one first approach considers a reliability criterion to expand the system, so that it operates in adequate conditions in the horizon planning while satisfying pre-defined limits in the reliability index. Transmission system reliability criterion regards to LOLE, which refers to the number of hours/days in a specified period of time (normally one year), in which the hourly/daily peak load possibly will exceed the available generation capacity. So, the planning problem considering reliability is formulated as an optimization problem that minimizes the investment subject to probabilistic reliability criterion. Reliability index for the transmission system is calculated for each configuration by subtraction of generation and bulk power reliability indexes. A composite power system effective load curve is used for reliability analysis of the bulk power system. This accumulate curve is obtained convolving two curves, one of them corresponding to a probability distribution function of the random outages of the system components, and the other one corresponding to the load duration curve. Reliability assessment in the generation system is done using a method that calculates the reliability index through the statistics moments of the frequency distribution of equivalents loads. This curve is obtained by convolving the generation units which are dispached in merit order. The proposed model is solved using the specialized genetic algorithm of Chu-Beasley (AGCB). Detailed results on two test systems are analyzed and discussed. A second approach to the transmission expansion... (Complete abstract click electronic access below) / Doutor

本論文研究如何建立一個投資組合用來追蹤穩定成長的目標線。我們將這個目標線追蹤問題建構成混合整數非線性數學規劃模型。由於用以追蹤目標線的投資組合，經過一段時間後其追蹤效能可能未如預期，本論文提出調整投資組合的數學規劃模型。這些模型中除了考量實務中的交易成本，亦考慮限制放空股票，所以將期貨加入投資組合中作為避險部位。最後，以台灣股票市場與期貨交易市場作為實證研究對象，探討投資組合建立與調整的表現，亦分析不同成長率設定之目標線與期貨投資比重上限對投資組合價值的影響。 / This thesis studies how to construct a tracking portfolio for the benchmark of a stable growth rate. This tracking problem can be formulated as a mixed-integer nonlinear programming model. Since the performance of the tracking portfolio may get worse when time elapses, this thesis proposes another mathematical programming model to rebalance the tracking portfolio. These models not only consider the transaction cost but also take into account of the limitation of shorting a stock; thus the tracking portfolio will include a futures position as a hedging position. Finally, an empirical study will be performed by using the data from the Taiwan stock market and the futures market to explore the performance of the proposed models. We will analyze how the different benchmark settings and the futures position limits will affect the value of the tracking portfolio.

本論文提出追蹤特定目標線的二階段混合整數非線性隨機規劃模型，以建立追蹤目標線的投資組合。藉由引進情境樹(scenario tree)，我們將此類二階段隨機規劃問題，轉換成為等價的非隨機規劃模型。在金融商品的價格波動及交互作用下，所建立的投資組合在經過一段時間後，其追蹤目標線的能力可能會日趨降低，所以本論文亦提出調整投資組合的規劃模型。為符合實務考量，本論文同時考慮交易成本、股票放空的限制，並且加入期貨進行避險。為了反應投資者的預期心理，也引進了選擇權及情境樹。最後，我們使用台灣股票市場、期貨交易市場及台指選擇權市場的資料進行實證研究，亦探討不同成長率設定之目標線與投資比例對於投資組合的影響。 / To construct a portfolio tracking specific target line, this thesis studies how to do it via two-stage stochastic mixed-integer nonlinear model. We introduce scenario tree to convert this stochastic model into an deterministic equivalent model. Under the volatility of price and the interaction of each financial derivatives, the performance of the tracking portfolio may get worse when time elapses, this thesis proposes another mathematical model to rebalance the tracking portfolio. These models consider the transactions cost and the limitation of shorting a stock, and the tracking portfolio will include a futures as a hedge position. To reflect the expectation of investors, we introduce scenario tree and also include a options as a hedge position. Finally, an empirical study will be performed by the data from Taiwan stock market, the futures market and the options market to explore the performance of the proposed models. We will analyze how the different benchmarks settings and invest ratio will affect the value of the tracking portfolio.

Made available in DSpace on 2014-06-11T19:30:50Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-25Bitstream added on 2014-06-13T19:19:30Z : No. of bitstreams: 1 garcesnegrete_lpg_dr_ilha.pdf: 1723635 bytes, checksum: ec9b369023c0d16cf9bcbe29a4bc0ada (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Nessa pesquisa tem-se por objetivo a análise teórica e a implementação computacional de duas propostas de solução ao problema de planejamento da expansão de sistemas de transmissão de energia elétrica considerando diferentes fatores relacionados com a confiabilidade do sistema e a adoção dos novos modelos de mercados elétricos. É importante notar, que no planejamento básico não são levados em conta esses importantes aspectos. Dessa forma, uma primeira aproximação considera um critério de confiabilidade para expandir o sistema, de forma que ele opere adequadamente no horizonte de planejamento satisfazendo um nível de confiabilidade pré-definido. O índice de confiabilidade utilizado para exigir esse nível de confiabilidade é o LOLE, que corresponde ao número médio de horas/dias em um período dado (normalmente um ano) no qual o pico da carga horária/diária do sistema possivelmente exceder´a a capacidade de geração disponível. O problema de planejamento considerando a confiabilidade é, portanto, formulado como um problema de otimização que minimiza o investimento sujeito ao critério de confiabilidade. O índice de confiabilidade para o sistema de transmissão é calculado para cada configuração, subtraindo o índice de confiabilidade do sistema de geração do sistema composto geração-transmissão (bulk power system ). Para calcular o índice no sistema composto geração transmissão, utiliza-se uma curva de duração de carga efetiva para este sistema. Esta curva acumulada de carga é obtida de um processo de convolução de outras duas curvas que representam a função de distribuição de probabilidade (FDP) das saídas aleatórias dos componentes do sistema e a curva de duração de carga, respectivamente. A avaliação de confiabilidade no sistema de geração é feita usando um método que calcula o índice de confiabilidade por meio dos momentos... / This work aims to the theoretical analysis and computational implementation of two proposals for the transmission expansion planning problem considering several factors such as system reliability and new electricity market structures. It is important to observe, that the basic planning does not consider these issues. Therefore, one first approach considers a reliability criterion to expand the system, so that it operates in adequate conditions in the horizon planning while satisfying pre-defined limits in the reliability index. Transmission system reliability criterion regards to LOLE, which refers to the number of hours/days in a specified period of time (normally one year), in which the hourly/daily peak load possibly will exceed the available generation capacity. So, the planning problem considering reliability is formulated as an optimization problem that minimizes the investment subject to probabilistic reliability criterion. Reliability index for the transmission system is calculated for each configuration by subtraction of generation and bulk power reliability indexes. A composite power system effective load curve is used for reliability analysis of the bulk power system. This accumulate curve is obtained convolving two curves, one of them corresponding to a probability distribution function of the random outages of the system components, and the other one corresponding to the load duration curve. Reliability assessment in the generation system is done using a method that calculates the reliability index through the statistics moments of the frequency distribution of equivalents loads. This curve is obtained by convolving the generation units which are dispached in merit order. The proposed model is solved using the specialized genetic algorithm of Chu-Beasley (AGCB). Detailed results on two test systems are analyzed and discussed. A second approach to the transmission expansion... (Complete abstract click electronic access below)

No description available.