الگوریتم نقطه داخلی برای برنامه ریزی خطی مورد استفاده در انتقال سنتز شبکه

This article presents a well-known interior point method (IPM) used to solve problems of linear programming that appear as sub-problems in the solution of the long-term transmission network expansion planning problem. The linear programming problem appears when the transportation model is used, and when there is the intention to solve the planning problem using a constructive heuristic algorithm (CHA), or a branch-and-bound algorithm. This paper shows the application of the IPM in a CHA. A good performance of the IPM was obtained, and then it can be used as tool inside algorithms used to solve the planning problem. Illustrative tests are shown, using electrical systems known in the specialized literature.

The expansion of electrical transmission systems should be based on an optimal plan, i.e., the plan should specify the transmission lines and/or transformers needed for the system to operate efficiently in relation to a given planning horizon. The parameters requiring consideration include the topology of the base year, candidate circuits, data about generation and demand for the planning horizon, and investment constraints. Thus, the solution for a planning problem should specify where, how much and when new equipment for expansion should be installed. There are two types of planning: static planning involves a single planning horizon, but multi-stage planning is a derived generalization considering the separation of the planning horizon into various stages. The expansion of transmission systems is generally modeled mathematically using the so-called DC model, which involves mixed non-linear programming, but its application is problematic for large-scale systems. Various modifications have thus been introduced, including relaxed versions of the DC power flow model. Greater details about the mathematical modeling of transmission system planning can be found in [1]. Many algorithms for the solution of problems involving the planning of transmission systems have been proposed in the specialized literature. These can be separated into three categories: (a) heuristic algorithms, (b) classic optimization algorithms such as Benders decomposition and branch and bound algorithms, and (c) meta-heuristic such as simulated annealing (SA), genetic algorithms (GA), and tabu search (TS). The focus of this research is the use of IPM algorithms in order to solve problems of linear and non-linear programming that appear as part of the solution process in algorithms used to solve the problem of long term transmission network expansion planning, also known as network transmission synthesis. Problems of linear programming (LP) or non-linear programming (NLP) should be usually solved in the implementation of the three categories algorithms used in the planning of transmission systems, mentioned earlier. In fact, the longer processing time spent by these algorithms happens while solving the problem of LP or NLP. The shape of these problems varies slightly according to the kind of optimization algorithm used to solve the planning problem. This article presents an IPM to solve a LP problem that appears when the constructive heuristic algorithm of Garver is used in the transportation model. The presented algorithm may be easily adapted to solve problems of LP that appear when there is the intention to solve the transportation model using an algorithm of branch-and-bound.

In this paper an IPM algorithm used as sub-routine in a CHA was presented and analyzed. The presented tests showed an efficient performance of the IPM algorithm. The presented algorithm is fast and robust. The performance of the algorithm increases with the adequate treatment of the data, for example, with the application of the p.u. system. An efficient LP solver such as the interior point algorithm based on predictor–corrector approach or the use of the LP solution as the initial point for the resolution of next LP problem represent fundamental strategies for the improvement of the method. All in all, it is important to notice that the algorithm showed to have qualities to be used inside the field of transmission network synthesis.