Advanced Methods for Energy Market Optimization
Optimization is performed as a routine in today’s electricity market environment. Examples are security constraint financial transmission rights (FTRs), unit commitment (UC), economic dispatch (ED), and AC optimal power flow (AC-OPF), an advanced form of ED. Non-linear systems such as those with large numbers of variables and constraints are among the most difficult computational problems known, belonging to the class of problems designated as non-deterministic, polynomial time hard (NP-Hard). At Pacific Northwest National Laboratory, we have developed a linear programming (LP) optimizer that scales better and is more easily parallelized than traditional simplex or interior point based methods.
Figure 1. PADS vs CPLEX performance with Commercial FTR dataset. Click for a larger image.
The Parallel Adaptive Dynamical System (PADS) solver has been applied to the FTR problem. FTRs are financial insurance tools to help power market participants reduce price risks associated with transmission congestion. FTRs are issued based on a process of solving a constrained optimization problem with the objective to maximize the FTR social welfare under power flow security constraints. Multiperiod problems combine different FTR categories (monthly, seasonal or annual), coupling independent blocks and the number of constraints increases quadratically with the number of categories. PADS can fully exploit the coupling structure whereas commercial software for FTR calculations cannot, resulting in a slowing as zero blocks are backfilled with non-zero values. PADS can also exploit the symmetry (cuts computation by a factor of two) and structure of the matrix related to obligatory bids (dense) and optional bids (sparse) other methods cannot. The PADS solver was used to solve the FTR problem for the standard Institute of Electrical and Electronics Engineers (IEEE) test systems, some synthetic Western Electricity Coordinating Council (WECC)-based systems, and real-world data from Alstom. The performance of PADS was comparable with the commercial software CPLEX© from IBM for small problems and dramatically outperformed the CPLEX dual simplex method on larger problems. This is because PADS scales better (the square of the problem size instead of the cube) and is more highly parallel while producing comparable results with no feasibility problems. Figure 1 shows the performance of PADS versus the CPLEX dual simplex method using data from a commercial FTR problem supplied by Alstom. The vertical axis is the value of the objective function (the FTR value), and the horizontal axis is the time in seconds required to reach the objective value. PADS, using 240 compute cores, gets very near the final answer in just a few seconds, while CPLEX takes over 300 times longer to achieve the same value. The CPLEX time per iteration slowed from 0.007 seconds at the beginning to 1.9 seconds near the end, an increase of 269 due to backfilling. PADS, however, has difficulty achieving the same level of accuracy in the final answer than CPLEX. Each method takes a different approach for adapting the original problem for solution. The sign of the objective function has been inverted for display purposes.
The success of PADS on FTR problems has attracted much interest in applying it to more difficult non-linear AC-OPF and mixed-integer unit commitment problems. Both of these have a linear solver at their core, typically a dual simplex or interior point method. We are in the process of adapting PADS to solve these problems.
S. T. Elbert, K. Kalsi, M. Vlachopoulou, M. J. Rice, K. R. Glaesemann, and N. Zhou, “Advanced computational methods for security constrained financial transmission rights: Structure and parallelism,” in Proceeding 8th Power Plants Power System Control Symposium, 2012, pp. 506–511.
K. Kalsi, S. Elbert, M. Vlachopoulou, N. Zhou, and Z. Huang, “Advanced computational methods for security constrained financial transmission rights,” in Proceeding IEEE Power Energy Society General Meeting, 2012.
S. Elbert, K. Kalsi, K. Glaesemann, M. Rice, M. Vlachopoulou, and N. Zhou, “Advanced methods for security constrained financial transmission rights (FTR),” presented at FERC workshop, Washington, DC, Jun. 25, 2012.
S. Elbert, “A more scalable approach to linear programming for energy market,” presented at Modeling, Simulation and Optimization for the 21st Century Electric Power Grid, Lake Geneva, Wisconsin, Oct. 21-25, 2012.
S. Elbert, K. Kalsi, and K. Glaesemann, “Duality based computational methods for security constrained financial transmission rights: a novel implementation,” presented at Advanced Grid Modeling Workshop, Knoxville, TN, Feb. 5-6, 2013.