With the deregulation of power industry and the market competition, reliable power supply and secured system operation are major concerns of the independent system operator (ISO) or decision-maker (DM). Power dispatch under deregulated environment is complicated with various possibilities of decisions involved. Without the assistance of Energy Management System (EMS), it is not easy for ISO or DM to operate with pure experiences. To enhance the operational efficiency, EMS involves the state-of-the-art control technology, and the fast and effective computer assisted decision support system will help dispatch the power. A conventional EMS has a few major tasks, among them, the ¡§network analysis¡¨ task and the ¡§forecast and scheduling¡¨ task are the most important in assisting the on-line power dispatch. In dealing with the new deregulated environment, an ¡§operational planning¡¨ has to be added to aid the EMS for more security. There are significant changes on EMS after deregulation. This dissertation will focus on the changes and new functions, in the ¡§network analysis¡¨ and the ¡§forecast and scheduling¡¨ tasks of an EMS, which supports the operation in the competitive environment. In the ¡§network analysis¡¨ task, we discuss the real and reactive power dispatch and congestion management with AC optimal power flow (OPF). In this task, the formulation of AC OPF with deregulation issues and the effect of flexible AC transmission systems (FACTS) devices are presented. A predictor-corrector interior-point nonlinear-programming (PCIPNLP) algorithm has been developed to solve the problem. The model involves only slight modification to the present OPF for social welfare maximization to obtain the optimized bid-based dispatch and nodal spot prices. The incorporation of FACTS devices for system operations can ease the difficulties caused by transmission congestion. It is found that PCIPNLP technique is very effective for the modified OPF solution for congestion relief under deregulation. In the ¡§forecast and scheduling¡¨ task, we discuss the resource scheduling for bid-based dynamic economic dispatch and spot dispatch for power and reserve. They can be formulated for social welfare maximizing problem that is solved by using an efficient interior point method. And the optimal resource allocation and nodal spot price can be given from the various test results. We have also proposed a fuzzy based strategic gaming method to determine the GenCo¡¦s bidding strategy. Based on fuzzy set theory, a multi-criteria decision-making method is used to obtain the optimal strategy combination, bids and expected payoffs. Decision maker can find the optimal strategy combination by using weight vector to represent his subjective attitude about the structure of multi-objectives. The advantages have also been demonstrated through the numerical examples. Compared with the classical (¡§nonfuzzy¡¨) game theory, the proposed approach could help the decision maker to obtain higher expected payoffs, and make his choices easily. Possible applications of the proposed fuzzy method can be suggested for other decision-making problems in the power systems

Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T18:52:54Z (GMT). No. of bitstreams: 1 Probst_RoyWilhelm_D.pdf: 708668 bytes, checksum: 4823f5bccb159edca170bcf52eb49f4c (MD5) Previous issue date: 2010 / Resumo: Um método de pontos interiores preditor-eorretor é desenvolvido para o problema de fluxo de potência ótimo ativo-reativo. As tensões são representadas em coordenadas cartesianas ao invés de coordenadas polares, pois estas, sendo quadráticas, permitem correções não lineares nas condições de factibilidade primai e dual e não apenas nas de complementaridade como nos métodos tradicionais de programação não-linear. Outra contribuição fornece uma nova heurística para o tratamento das restrições de magnitude das tensões. Experimentos computacionais com sistemas de teste IEEE e um sistema real brasileiro são apresentados e mostram as vantagens do método proposto / Abstract: A predictor-corrector interior-point method is developed to the AC active and reactive optimal power flow problem. Voltage rectangular coordinates is adopted instead of polar ones, since, being quadratic, it allows nonlinear corrections for the primal and dual feasibility conditions and not only for the complementary constraints as in the traditional nonlinear programming methods. A new heuristic is proposed to handle voltage magnitude constraints. Computational experiments for IEEE test systems and a real Brazilian system are presented showing the advantages of the proposed approach / Doutorado / Pesquisa Operacional / Doutor em Matemática Aplicada

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-04-28T17:57:49Z No. of bitstreams: 1 erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-05-02T01:13:24Z (GMT) No. of bitstreams: 1 erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5) / Made available in DSpace on 2016-05-02T01:13:24Z (GMT). No. of bitstreams: 1 erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5) Previous issue date: 2015-11-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho apresentamos um estudo da influência dos parâmetros de um algoritmo de pontos interiores e direções viáveis para solução de problemas de otimização não linear. Esse algoritmo, denominado FDIPA, tem por objetivo encontrar dentre os pontos de um conjunto definido por restrições de igualdade e/ou desigualdade, aqueles que minimizam uma função diferenciável. O FDIPA baseia-se na resolução de dois sistemas de equações lineares com a mesma matriz de coeficientes, obtidos das condições necessárias de primeira ordem de Karush-Kuhn-Tucker. A partir de um ponto inicial no interior do conjunto viável, o FDIPA gera uma sequência de pontos também interiores ao conjunto. Em cada iteração, uma nova direção de descida é obtida e, em seguida, produz-se uma deflexão da direção de descida no sentido do interior do conjunto viável, de modo a se obter uma nova direção que seja de descida e viável. Realiza-se então uma busca linear para obter um novo ponto interior e garantir a convergência global do método. Uma família de algoritmos pode ser obtida variando-se as regras de atualização dos parâmetros do FDIPA. O estudo apresentado neste trabalho foi feito considerando-se um único algoritmo e com restrições de desigualdade somente. Testes numéricos apontaram para uma escolha de parâmetros que levou a um número menor de iterações na resolução dos problemas teste. / This work presents a study on the influence of the parameters of an interior point and feasible directions algorithm for solving non-linear problems. The algorithm, named FDIPA, aims to find among the points of a set defined by equality and/or inequality constraints, those which minimize a differentiable function. The FDIPA is based on two linear systems with the same coefficient matrix, obtained from the Karush-Kuhn-Tucker first order necessary conditions. From a initial point in the interior of the feasible set, FDIPA generates a sequence of points which are also interior to the set. At each iteration, FDIPA produces a descent direction which is deflected towards the interior of the feasible set in order to create a new descent and feasible direction. Then, a linear search is performed to get a new interior point and assure the global convergence of the method. A family of algorithms can be obtained varying the rules used to update the parameters of the FDIPA. The study presented here has been done considering just one particular algorithm and inequality constraints only. Numerical tests pointed to a certain choice of parameters which led to a fewer number of iterations when solving some test problems.

Orientadores: Aurelio Ribeiro Leite de Oliveira, Fredy Angel Amaya Robayo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-23T17:46:00Z (GMT). No. of bitstreams: 1 MamianLopez_EstherSofia_M.pdf: 1176541 bytes, checksum: 8f49901f40e77c9511c30e86c0d1bb0d (MD5) Previous issue date: 2013 / Resumo: Os modelos probabilísticos de uma linguagem (MPL) são modelos matemáticos onde é definida uma função de probabilidade que calcula a probabilidade de ocorrência de uma cadeia em uma linguagem. Os parâmetros de um MPL, que são as probabilidades de uma cadeia, são aprendidos a partir de uma base de dados (amostras de cadeias) pertencentes à linguagem. Uma vez obtidas as probabilidades, ou seja, um modelo da linguagem, existe uma medida para comparar quanto o modelo obtido representa a linguagem em estudo. Esta medida é denominada perplexidade por palavra. O modelo de linguagem probabilístico que propomos estimar, está baseado nas gramáticas probabilísticas livres do contexto. O método clássico para estimar os parâmetros de um MPL (Inside-Outside) demanda uma grande quantidade de tempo, tornando-o inviável para aplicações complexas. A proposta desta dissertação consiste em abordar o problema de estimar os parâmetros de um MPL usando métodos de pontos interiores, obtendo bons resultados em termos de tempo de processamento, número de iterações até obter convergência e perplexidade por palavra / Abstract: In a probabilistic language model (PLM), a probability function is defined to calculate the probability of a particular string ocurring within a language. These probabilities are the PLM parameters and are learned from a corpus (string samples), being part of a language. When the probabilities are calculated, with a language model as a result, a comparison can be realized in order to evaluate the extent to which the model represents the language being studied. This way of evaluation is called perplexity per word. The PLM proposed in this work is based on the probabilistic context-free grammars as an alternative to the classic method inside-outside that can become quite time-consuming, being unviable for complex applications. This proposal is an approach to estimate the PLM parameters using interior point methods with good results being obtained in processing time, iterations number until convergence and perplexity per word / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Dans cette thèse, une méthode de résolution de problèmes de commande optimale non linéaires sous contraintes d'état et de commande. Cette méthode repose sur l'adaptation des méthodes de points intérieurs, utilisées en optimisation de dimension finie, à la commande optimale. Un choix constructif de fonctions de pénalisation intérieure est fourni dans cette thèse. On montre que ce choix permet d'approcher la solution d'un problème de commande optimale sous contraintes en résolvant une suite de problèmes de commande optimale sans contraintes dont les solutions sont simplement caractérisées par les conditions de stationnarité du calcul des variations.Deux études dans le domaine de la gestion de l'énergie dans les bâtiments sont ensuite conduites. La première consiste à quantifier la durée maximale d'effacement quotidien du chauffage permettant de maintenir la température intérieure dans une certaine bande de confort, et ce pour différents types de bâtiments classés de mal à bien isolés. La seconde étude se concentre sur les bâtiments BBC et consiste à quantifier la capacité de ces bâtiments à réaliser des effacements électriques complets du chauffage de 6h00 à 22h00 tout en maintenant, là encore, la température intérieure dans une bande de confort. Cette étude est réalisée sur l'ensemble de la saison de chauffe. / This thesis exposes a methodology to solve constrained optimal controlof non linear systems by interior penalty methods. A constructivechoice for the penalty functions used to implement the interior methodis exhibited in this thesis. It is shown that itallows us to approach the solution of the non linear optimal controlproblem using a sequence of unconstrained problems, whose solutionsare readily characterized by the simple calculus of variations.Two representatives study of energy management in buildings are conducted using the provided algorithm. The first study consists in quantifying the maximal duration of daily complete load shiftings achievable by several buildings ranging from poorly to well insulated. The second study focuses on low consumption buildings and aim at quantifying the ability of these buildings to perform complete load shiftings of the heating electrical consumption from the day (6 a.m. to 10 p.m.) to the night period over the whole heating season.

Network utility maximization has emerged as a powerful tool in studying flow control, resource allocation and other cross-layer optimization problems. In this work, we study a flow control problem in the optimization framework. The objective is to maximize the sum utility of the users subject to the flow constraints of the network. The utility maximization is solved in a distributed setting; the network operator does not know the user utility functions and the users know neither the rate choices of other users nor the flow constraints of the network. We build upon a popular decomposition technique proposed by Kelly [Eur. Trans. Telecommun., 8(1), 1997] to solve the utility maximization problem in the aforementioned distributed setting. The technique decomposes the utility maximization problem into a user problem, solved by each user and a network problem solved by the network. We propose an iterative algorithm based on this decomposition technique. In each iteration, the users communicate to the network their willingness to pay for the network resources. The network allocates rates in a proportionally fair manner based on the prices communicated by the users. The new feature of the proposed algorithm is that the rates allocated by the network remains feasible at all times. We show that the iterates put out by the algorithm asymptotically tracks a differential inclusion. We also show that the solution to the differential inclusion converges to the system optimal point via Lyapunov theory. We use a popular benchmark algorithm due to Kelly et al. [J. of the Oper. Res. Soc., 49(3), 1998] that involves fast user updates coupled with slow network updates in the form of additive increase and multiplicative decrease of the user flows. The proposed algorithm may be viewed as one with fast user update and fast network update that keeps the iterates feasible at all times. Simulations suggest that our proposed algorithm converges faster than the aforementioned benchmark algorithm. When the flows originate or terminate at a single node, the network problem is the maximization of a so-called d-separable objective function over the bases of a polymatroid. The solution is the lexicographically optimal base of the polymatroid. We map the problem of finding the lexicographically optimal base of a polymatroid to the geometrical problem of finding the concave cover of a set of points on a two-dimensional plane. We also describe an algorithm that finds the concave cover in linear time. Next, we consider the minimization of a more general objective function, i.e., a separable convex function, over the bases of a polymatroid with a special structure. We propose a novel decomposition algorithm and show the proof of correctness and optimality of the algorithm via the theory of polymatroids. Further, motivated by the need to handle piece-wise linear concave utility functions, we extend the decomposition algorithm to handle the case when the separable convex functions are not continuously differentiable or not strictly convex. We then provide a proof of its correctness and optimality.

Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1 Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5) Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.

Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.