Neste trabalho será apresentado um algoritmo de pontos interiores para a solução do problema de fluxo de carga ótimo (FCO). A abordagem proposta é o método primai dual barreira logarítmica. As restrições de desigualdade do problema de FCO são transformadas em igualdades pelo uso de variáveis de folga, e estas são incorporadas na função objetivo através da função barreira logarítmica. A esparsidade da matriz Lagrangeana é explorada e o processo de fatoração é feito por elementos e não por submatrizes. Resultados numéricos de testes realizados em sistemas de 3, 14, 30 e 118 barras serão apresentados com o objetivo de mostrar a eficiência do método. / In this thesis an interior point algorithm is presented for the solution of the optimal power flow problem (OPF). The approach proposed here is the logarithmic barrier primal-dual method. The inequality constraints of the optimal power flow problem are transformed into equalities by slack variables that are incorporated into the objective function through the logarithmic barrier function. The sparsity of the Lagrangian matrix is explored and the factorization process is carried out by elements rather than submatrices. Numerical tests results obtained with systems of 3, 14, 30 and 118 buses are presented to show the efficiency of the method.

Orientador: Aurelio R. Leite Oliveira, Marta Ines Velazco / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T08:57:24Z (GMT). No. of bitstreams: 1 Silva_Jairda1_D.pdf: 1755258 bytes, checksum: 2ecb493aab3646838f54c2df2012b5d9 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho apresentamos uma nova família de algoritmos para resolver problemas de programação linear. A vantagem desta família de algoritmos é a sua simplicidade, a possibilidade de explorar a esparsidade dos dados do problema original e geralmente possuir raio de convergência inicial rápido. Esta família de algoritmos surgiu da generalização da idéia apresentada por João Gonçalves, Robert Storer e Jacek Gondzio, para desenvolver o algoritmo de ajustamento pelo par ótimo. Este algoritmo foi desenvolvido por sua vez tendo como base o algoritmo de Von Neumann. O algoritmo de Von Neumann possui propriedades interessantes, como simplicidade e convergência inicial rápida, porém, ele não é muito prático para resolver problemas lineares, visto que sua convergência é muito lenta. Do ponto de vista computacional, nossa proposta não é utilizar a família de algoritmos para resolver os problemas de programação linear até encontrar uma solução e sim explorar a sua simplicidade e seu raio de convergência inicial geralmente rápido e usá-la em conjunto com um método primal-dual de pontos interiores infactível, para melhorar a eficiência deste. Experimentos numéricos revelam que ao usar esta família de algoritmos em conjunto com um método primal-dual de pontos interiores infactível melhoramos o seu desempenho na solução de algumas classes de problemas de programação linear de grande porte. / Abstract: In this work, we present a new family of algorithms to solve linear programming problems. The advantage of this family of algorithms relies in its simplicity, the possibility of exploiting the sparsity of the original problem data and usually to have fast initial ratio of convergence. This family of algorithms arose from the generalization of the idea presented by João Gonçalves, Robert Storer and Jacek Gondzio to develop the optimal pair adjustment algorithm. This algorithm was developed in its own turn based on the Von Neumann's algorithm. It has interesting properties, such as simplicity and fast initial convergence, but it is not very practical for solving linear problems, since its convergence is very slow. From the computational point of view, our suggestion is not to use the family of algorithms to solve problems of linear programming until optimality, but to exploit its simplicity and its fast initial ratio of convergence and use it together with a infeasible primal-dual interior point method to improve its efficiency. Numerical experiments show that using this family of algorithms with an infeasible primal-dual interior point method improves its performance in the solution of some classes of large-scale linear programming problems. / Doutorado / Doutor em Matemática Aplicada

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19122号 / 情博第568号 / 新制||情||100(附属図書館) / 32073 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

No description available.

Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).

Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).

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

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.

Este trabalho tem por objetivo estudar e analisar a influência do parâmetro de barreira e de seu fator de correção no processo de convergência dos métodos de pontos interiores primal-dual, primal-dual barreira modificada e primal-dual barreira modificada com as técnicas preditor-corretor e Newton composto. A grande motivação para o desenvolvimento desta pesquisa está relacionada com a busca de métodos eficientes para resolver problemas de otimização de programação não-linear, existentes na área de engenharia elétrica mais especificamente na operação de sistemas elétricos de potência. Esses métodos foram aplicados a um problema de programação não-linear e aos sistemas elétricos de três e de trinta barras para analisar a sensibilidade em relação ao parâmetro de barreira e ao seu fator de correção. / This work has for objective to study and to analyze the influence of the barrier parameter and its correction factor in the convergence process of the methods primal-dual interior point, primal-dual modified barrier and primal-dual barrier modified with the techniques predictor-corrector and composed Newton. The great motivation for the development of this research is related with the search of efficient methods to solve nonlinear programming optimization problems, existent in the area of electric engineering more specifically in the operation of power systems. Those methods were applied to a nonlinear programming problem and the electric systems of three and thirty buses to analyze the sensibility in relation to the barrier parameter and its correction factor.