1 Introduction

Worldwide, the electric power industry has witnessed significant changes over the course of the past two decades. Deregulated electricity markets, first introduced in Chile in 1990, are now commonplace. These competitive markets reduce costs, but they also bring uncertainty to generation forecasting as power producers compete to sell electricity. Meanwhile, in many places, consumer demand has outpaced infrastructure development, placing pressure on aging equipment. In addition, the increased penetration of non-dispatchable renewable sources, such as wind and solar, adds another degree of complexity to the scheduling of power flows. All these factors contribute to the increasing need for fast and reliable optimization methods, tools, and software that can address both security and economic issues simultaneously in support of power system operation and control [149]. Optimal Power Flow (OPF) has been the predominant method for such analysis since its introduction by Carpentier in 1962 [26]. Optimization methods have been widely used in power system operation, analysis, and planning [48, 158]. However, existing OPF solution methods a often prove inadequate for the increased complexity of modern OPF problems.

OPF seeks to optimize a given cost, planning, or reliability objective by controlling power flow within an electrical network without violating network power flow constraints or system and equipment operating limits. Like conventional power flow analysis, OPF determines voltage, current, and injected power throughout an electrical power system, that is, the system’s state of operation. However, unlike conventional power flow, OPF works with an underconstrained system: multiple solutions are possible. OPF therefore performs multiple power flow iterations, modifying the underconstrained variables in order to advance the objective.

The general OPF problem is a nonlinear, non-convex, large-scale optimization problem which may contain both continuous and discrete control variables [16]. Many different OPF formulations have been developed to address specific instances of the problem, using varying assumptions and selecting different objective functions, controls, and system constraints. The resulting optimization problems go by many names depending on the particular objective function being addressed and the constraints under consideration. Regardless of the name, however, any power systems optimization problem that includes a set of power flow equations in the constraints may be classified as a form of OPF.

Many OPF solution methods have also been developed, each with distinct mathematical characteristics and computational requirements. Almost every mathematical programming approach that can be applied to OPF has been attempted and it has taken developers many decades to develop software capable of solving OPF problems reliably [164]. Today, OPF studies and methods present flexible and powerful tools which are widely used in industry applications, such as constrained economic dispatch and voltage control problems [147]. However, real-life OPF problems are often significantly more challenging than the classically considered problems and OPF methods vary considerably in their adaptability to the modeling and solution requirements of different engineering applications. Therefore, to date, there has been no single formulation and solution approach suitable for all the various forms of OPF problems.

The difficulty of solving OPF problems increases significantly with increasing network size and complexity. Recent industry developments have greatly increased electric power system complexity, pushing this issue to the forefront of OPF research. In prior decades, utilities typically had relatively few generators compared to the numbers introduced today by the advent of independent power producers and large-scale integration of distributed and renewable generation. Meanwhile, demand response programs add variables to the load side of OPF problems. In addition, network power flow constraints must incorporate advanced controls such as Flexible AC Transmission Systems (FACTS) devices. Unfortunately, these developments have discouraged the use of OPF in many real-world applications [10, 123].

In this survey, we examine OPF formulations and their solution techniques from an operations research perspective. There is a wide variety of OPF formulations and optimization methods available in the literature with respect to these modern challenges, and the huge body of literature published in the past four decades precludes the inclusion of an exhaustive list of publications within this survey. Instead, this survey attempts a comprehensive overview of the optimization techniques applied to OPF problems, illustrating each technique with a few key publications. In this way, this survey is an extension of the book chapter [120] by way of the variety of methods surveyed.

Several review papers of OPF were published in the 1990s: [34, 46, 67, 102, 103]. Zhang and Tolbert [180] surveyed a number of OPF methods, describing the methodology of each in detail. More recently, Zhang [184] summarized the common deterministic OPF methods while Xia and Elaiw [167] reviewed the optimal power dynamic dispatch problem, including discussion of random search methods. Pandya and Joshi [113] and Qiu et al. [119] have also surveyed several of the key algorithms used to solve OPF problems. This survey differs from previous work in that it focuses more specifically on cataloging and discussing the literature associated with the various solution methods. To the best knowledge of the authors, this survey is the most comprehensive review of OPF algorithms for electric power systems available in the literature to date, both in the number of referenced articles as well as in the number of methods surveyed. (Although the concept of OPF has also been extended beyond electric power systems [52], this survey does not examine such work.)

In writing this survey, our aim has been to provide a starting reference and a rich resource for the operations researcher who may be unfamiliar with OPF. While bibliographic search engines provide a similar listing of references, they do not provide context to aid the reader in locating the best articles to read first. In this survey, we summarize the contributions of each article cited so that the reader may readily discern whether a given article is relevant to his or her research needs. For the reader interested in finding more articles on OPF beyond those referenced here, we suggest searching the following journals:

  • IEEE Transactions on Power Systems (formerly IEEE Transactions on Power Apparatus and Systems),

  • International Journal of Electrical Power & Energy Systems,

  • Electric Power Systems Research, and

  • Energy Conversion and Management.

These journals have the largest volume of OPF literature among the publications surveyed.

Part I of the survey (this article) provides a general introduction to the OPF problem, describes the key requirements for OPF methods, and surveys deterministic optimization methods that have been applied to OPF. Part II of the survey examines the trend towards stochastic, or non-deterministic, search techniques and hybrid methods (including combinations of deterministic methods) that has occurred in the last two decades and gives the survey conclusions [49].

The remainder of this article is organized as follows: In Sect. 2, we briefly discuss the general mathematical programming framework and characteristics of OPF problems. In Sect. 3, we describe desirable characteristics of OPF methods, especially in relation to recent industry developments. In Sect. 4, we focus on deterministic (classical) optimization methods which have been applied to OPF. We first describe the applied methodology and, second, we survey the relevant literature. While some paragraphs discuss the papers in chronological order, others highlight streams of research. We summarize the deterministic methods with Sect. 5, however, we refer readers to part II of the survey for conclusions [49]. Various abbreviations used throughout this article are summarized above.

2 Formulations of OPF problems

2.1 Notation

We use the following notation in the discussion of OPF formulations and power flow equations:

u :

controllable system variables

x :

dependent or state variables

f(u,x):

objective function

g(u,x):

vector function of equality constraints

h(u,x):

vector function of inequality constraints

N :

total number of system buses

i,k :

indices corresponding to system buses

j :

the imaginary unit or 90∘ operator, \(\sqrt{-1}\)

P i :

real power injected at bus i (generation − load)

Q i :

reactive power injected at bus i (generation − load)

V i :

voltage phasor at bus i

δ i :

voltage angle at bus i

E i :

real component of complex voltage at bus i

F i :

imaginary component of complex voltage at bus i

Note: |V|∠δ=E+jF

Y ik :

ikth element of the bus admittance matrix

θ ik :

angle of ikth element of the bus admittance matrix

G ik :

conductance (real component) of Y ik

B ik :

susceptance (imaginary component) of Y ik

Note: |Y|∠θ=G+jB

2.2 General structure

The majority of OPF formulations may be represented using the following standard form [81, 181]:

The objective function f(u,x) represents the system’s optimization goal. f is usually a scalar function, but in multi-objective OPF it may be interpreted as a vector function. Vector functions g(u,x) and h(u,x) represent system equality and inequality constraints, respectively. Depending on the selection of f, g, and h, the OPF problem may become a linear, mixed integer-linear, nonlinear (likely non-convex), or mixed integer-nonlinear programming problem; these cases are discussed in more detail in Sect. 2.6.

In general, the computational challenge of solving an OPF formulation increases substantially with the accuracy of the system representation. The presence of non-convexity in the objective(s) and constraints make OPF problems especially challenging, both computationally and theoretically [5]. In addition, structurally “complicated” constraints are difficult to handle in random or stochastic search techniques. As a workaround, such constraints are often applied as penalties to the objective function.

2.3 Variables

All OPF formulations require variables to represent the electrical state of the system. These electrical state variables are continuous. Most often, the state variables of choice are bus voltage magnitude, bus voltage angle, and real and reactive power injections at each bus. This representation is used in most early OPF formulations and is also the most common representation found in recent papers [6, 18, 19, 26, 45, 145]. Alternative choices of state variables include current injections instead of power injections or the representation of voltages in rectangular coordinates [76]. The choice of state variables is dictated by the form of the power flow equations used.

Controllable variables typically include a subset of the state variables (for example, real and reactive power injections at generation buses) as well as variables representing control device settings, such as transformer tap ratios. Control variables may be continuous or discrete; in the case of switched devices or lines they are binary. Control variables differ widely among OPF formulations based on the nature of the particular problem under consideration. Table 1 summarizes the variables found in the literature together with representative references.

Table 1 OPF problem variables with selected references
Full size table

2.4 Objective function

The most common OPF objective is the minimization of generation costs, with or without consideration of system losses. In this way, OPF extends the classic economic dispatch problem: classic economic dispatch controls only which generation units to dispatch while OPF controls all power flows within the system [18, 184]. (In recent papers, the term “economic dispatch” is sometimes applied to OPF which has the same objective function as the classic economic dispatch problem.) Generation cost functions are often approximated using quadratic cost curves [76, 112], or with piecewise linear sections [7].

However, many other OPF objectives are possible [184]. Besides minimization of generation costs, the more common objectives include minimization of system losses, maximization of power quality (often by minimizing voltage deviation), and minimization of capital costs during system planning. Table 2 summarizes the objective functions found in the literature together with representative references. In nearly all cases, the objectives are functions of the system real and reactive power generation.

Table 2 OPF problem objectives with selected references
Full size table

2.5 Constraints

OPF constraints may be categorized into equality constraints and inequality constraints, summarized in Table 3. Equality constraints g(u,x) include the power flow network equations and any other balance constraints. Several variations of the power flow equations are present in the literature. The full version of the power flow equations is the alternating current (AC) power flow. OPF formulations incorporating the AC power flow equations are both nonlinear and non-convex.

Table 3 OPF problem constraints with selected references
Full size table

The majority of OPF formulations use the polar form of AC power flow:

(1)
(2)

The polar form is associated with the choice of voltage magnitude |V| and voltage phase angle δ as state variables. A few recent papers use the rectangular form of AC power flow instead [76, 131, 150]:

(3)
(4)

In the rectangular form, bus voltages are represented by their real and imaginary components E and F rather than by magnitude and phase angle. The rectangular form has the advantage of eliminating trigonometric functions from the constraint set and of having constant second partial derivatives. Control elements, such as phase shifters or variable transformer tap ratios, are often incorporated into (1)–(4) via appropriate modifications to the admittance matrix elements. The power flow equations for OPF are discussed in more detail in several textbooks [124, 164, 189].

In practical transmission systems, (1)–(2) exhibit an interesting and useful property: changes in real power P are strongly coupled to changes in voltage angle δ while changes in reactive power Q are strongly coupled to changes in changes in voltage magnitude |V| [184]. This is true because the angles θ of admittance matrix elements are typically near 90∘ (or −90∘) and adjacent bus voltage angles are typically close together. As a result, the flow of system real power may be “decoupled” from the flow of reactive power: real power becomes a function of δ and reactive power a function of |V|. The OPF problem may then be decomposed into subproblems for the real and reactive power flows [18]. Many OPF algorithms take advantage of this decomposition because it provides significant algorithm simplification while introducing only a small amount of error. In particular, the reactive subproblem, called optimal reactive power flow (ORPF), is often analyzed as a standalone problem. However, the decoupled approach to OPF is not typically accurate when complex control devices are present in the system [184].

Direct current (DC) power flow extends the decoupling principle to form a linear OPF constraint set.Footnote 1 The DC power flow equations are obtained by applying two assumptions: (i) the elements of the admittance matrix Y are purely imaginary and (ii) the difference between adjacent bus voltage angles is small. Under these assumptions, Y ik =jB ik , sin(δ i −δ k )≈δ i −δ k , and cos(δ i −δ k )≈1. The resulting network equations are bilinear in terms of voltage magnitude and angle:

(5)
(6)

In most cases, only the real power flow is considered and all bus voltage magnitudes in (5) are approximated as 1.0. This results in the fully linearized DC power flow equation:

(7)

Use of DC power flow is attractive because it allows the development of a fully linear constraint set. Many commercial and industry OPF formulations use the DC power flow equations instead of AC power flow [12, 123, 124]. However, the simplifying assumptions both neglect network losses and prevent accurate cost accounting for reactive power [123]. Neglecting network losses introduces unacceptable levels of error in large power system models [143].

Several methods are available to enhance the DC power flow equations to provide an estimate of system losses [35, 143]. The majority of these techniques require the use of AC power flow to provide a reference point at which to fix the system losses for use in the DC power flow. With such enhancements, the overall performance of DC power flow can be very good for accurately modeling MW flows. However, even if the average error is minimal, very large errors in the model can occur for certain branches in the power system [143].

The inequality constraints h(u,x) include minimum and maximum limits on control and state variables, such as bus voltage and line current magnitudes. Steady-state stability constraints may be included as additional sets of power flow equations where the admittance matrix has been modified to reflect specific contingency cases [6]. This adds both equality and inequality constraints to the formulation. Other work has focused on incorporating transient stability constraints, often using iterative techniques [95, 104, 142]. However, many transient security constraints may now be incorporated directly into h analytically, eliminating the need for external security monitoring or additional iterations during the optimization process [32, 50].

2.6 Classification of OPF formulations

As previously noted, OPF formulations differ greatly depending on the particular selection of variables, objective(s), and constraints. Because of the specialized nature of OPF, the formulation selected often has implications for both solution method design and solution accuracy. Here we identify and discuss the classes of formulations found in the literature in order to provide context for the solution methods discussed in Sect. 4.

2.6.1 Nonlinear programming

The classic OPF formulation introduced by Carpentier [26] and used in the earliest papers discussing OPF solution methods is a continuous nonlinear programming (NLP) formulation [45]. Discrete variables such as transformer tap settings are approximated as continuous for algorithmic simplicity. The variables are often divided into a set of decision variables and a set of state variables, with the two sets related by the power flow equations [164]. This approach reduces the set of variables on which the optimization algorithm must operate and may improve the convexity characteristics of the problem.

The main advantage of NLP formulations for OPF is that they accurately capture power system behavior. However, the computational and theoretical challenges associated with NLP motivated the development of simplified formulations, as discussed below. In addition, certain NLP formulations redefine the problem variables to reduce the degree of nonlinearity, thereby improving the computational aspects of the problem, [9, 71, 90].

Recently, Lavaei and co-workers published a series of papers, where a globally optimal solution for the OPF problem (under some mild conditions) can be obtained by solving the dual problem. The dual problems are (convex) semidefinite programming problems. The clue is that a zero duality gap can be proven under the condition that the dual posses a solution that a certain semidefinite matrix has a zero eigenvalue of multiplicity two. It turns out that this condition is satisfied for the IEEE benchmark systems when a small resistance is added to all transformers that originally possess a zero resistance [82, 83, 137].

2.6.2 Linear programming

Although the OPF problem is natively nonlinear and non-convex, linear programming (LP) formulations for OPF are attractive because they allow the use of well-developed LP solution methods, such as the Simplex Method. Such methods are highly desirable for many reasons: efficient handling of inequality constraints, quick recognition of problem infeasibility, speed, reliability, and (especially) excellent convergence properties. In addition, LP formulations are convex, and therefore guarantee a global optimal solution.

Any LP formulation for OPF involves simplifying assumptions and linearization. The simplest and most direct application of LP to OPF is the use of the DC power flow formulation discussed in Sect. 2.5 with a linear (or linearized) objective function [124]. Since the DC power flow constraint set is fully linear, no further constraint linearization is needed. In contrast to other linearization techniques, DC-OPF is non-iterative; only a single solve is required to yield the optimal solution. Because of its simplicity, speed, and robust nature, DC-OPF is widely used in industry [123]. Another common technique is to linearize the power system equations around the current operating point [143, 164]; this forms the basis for many OPF algorithms that employ sequential linear programming (SLP).

While simplified formulations are adequate for some OPF problems, in many cases the simplifications seriously compromise the accuracy of the solution. LP approaches work quite well in case of separable and convex objective functions, such as the minimization of the total generation costs. However, in case of non-separable objective function—for instance, the minimization of the transmission losses—LP based OPF formulations are not as effective, producing significant inaccuracy. In such cases, the implementation of the algorithm must be done carefully to obtain a meaningful solution [42].

Additionally, the global optimal solution of the LP formulation is not guaranteed to be the global optimum of the original NLP problem, and may not even be a feasible solution at all. It is also difficult to model complex power systems controls using LP. These limitations restrict the applicability of LP methods for many OPF applications [101, 180]. Nevertheless, through careful formulation and algorithm development, LP methods have been widely applied to OPF with success.

2.6.3 Quadratic programming

Quadratic programming (QP) is a special form of nonlinear programming in which the objective function is quadratic of the form \(\frac{1}{2}x^{T} Q x + q^{T}x\) and all constraints are linear. In general, if matrix Q is positive semidefinite, then the corresponding quadratic program is convex and its optimal solutions are completely characterized by the Karush-Kuhn-Tucker (KKT) conditions. However, if the matrix Q is not positive semidefinite, the quadratic program may have many local minima and algorithms typically cannot guarantee global optimality [65].

QP-based OPF was introduced as alternative to LP for cases where LP formulations perform poorly, such as for loss minimization. Like LP, QP requires a local linearization of the power system constraints, and therefore suffers from many of the same accuracy issues. However, QP can directly represent quadratic objective functions, such as generator cost functions. Besides more accurately representing the true objective function, this also allows QP-based algorithms to converge in some cases where LP-based methods would diverge.

Glavitsch and Spoerry [53] demonstrated a non-sparse QP OPF formulation based on incremental power flow, using the rectangular power flow formulation, while Burchett et al. [19] presented a sparse implementation for large-scale power systems suitable for use with sequential quadratic programming (SQP). Contaxis et al. [37] implemented a decoupled QP formulation. The decoupled subproblems are suitable for SQP or, if linearized cost curves are used, for SLP. The decoupled formulation is similar to that described in [19], but Contaxis et al. discuss the functional form of the constraints in detail.

2.6.4 Mixed integer linear programming

Continuous LP, QP, and NLP formulations cannot accurately model discrete control elements, such as transformer tap ratios or switched capacitor banks. Discrete variables present one of the most challenging aspects of OPF. Capitanescu and Wehenkel [21] discuss some heuristic techniques that have been used to deal with discrete variables. However, none of these methods is entirely satisfactory. For example, the common technique of approximating discrete variables as continuous and then rounding them to the nearest discrete value may lead to suboptimal or even infeasible solutions [21].

Another option is to linearize the system and applied mixed integer linear programming (MILP) techniques. These MILP formulations are often solved with sequential approach similar to SLP. MILP retains many of the benefits of LP while also accommodating discrete variables. However, like LP, MILP formulations cannot fully represent the nonlinearity of the power system, and therefore suffer some inherent inaccuracy. Lobato et al. [92] presented an MILP formulation for capacitor control action suitable for an SLP-type approach, while Zhang and Ren [88] demonstrated a MILP formulation for optimal phase shifter placement based on the DC power flow equations.

2.6.5 Mixed integer nonlinear programming

It is mixed integer nonlinear programming (MINLP), however, that provides the most accurate, and most complex, way to represent power systems with discrete control elements. Unfortunately, mixed integer nonlinear programs are by far the most difficult type of optimization problem. Therefore, there is a strong tradeoff between system accuracy and problem tractability. MINLP formulations are commonly used with the nondeterministic (heuristic) solution approaches discussed in Part II of this survey, but are much less commonly used with deterministic methods.

Unfortunately, few papers give clear, complete MINLP formulations for the OPF problems described and solved. However, we refer the interested reader to Rashidi and El-Hawary [122] and Subbaraj and Rajnarayanan [144] for reasonable examples of MINLP OPF formulations. Additionally, security-constrained unit commitment (SCUC) is a special case of MINLP OPF where future generation is committed (scheduled) subject to power system constraints and generator operating constraints. Committed units (generators) are modeled using integer variables, hence the need for an MINLP formulation. The SCUC problem is one of the most important for power systems operators as well as one of the most difficult to solve. Bai and Wei [11] provide a thorough discussion of SCUC, including a detailed formulation.

3 Requirements for OPF methods

As electric power systems migrate from vertically integrated utilities to competitive market structures, they place increasingly complex demands on OPF algorithms. The presence of bottlenecks in the grid affects the total supply cost, limiting production of the least expensive plants and forcing the dispatch of more costly generation. In response, utilities have introduced FACTS devices and other sophisticated controls to alleviate bottlenecks and maximize line utilization [184]. These controls must be accounted for within OPF formulations. Simultaneously, utilities are using more complex models for generation and distribution equipment. These models are often empirical, and may not have derivatives or explicit formulations. Incorporation of such models also greatly increases OPF complexity.

Competitive markets and the rise of renewable generation have also greatly increased system complexity through the introduction of more generators and interconnections. Distributed generation is particularly problematic because it requires that portions of the distribution system be modeled in addition to the transmission network. The resulting system models can have many more variables than in previous decades, but are nevertheless more tightly constrained as demand outpaces growth in transmission capacity.

This increase in power system size and complexity has prevented full AC-OPF from being widely adopted in real-time operation. Instead, system operators often use simplified DC-OPF tools [123]. Originally, AC-OPF was not used due to a lack of efficient AC-OPF algorithms and sufficiently powerful computer hardware. Now, however, the primary concern is algorithm robustness [5], especially when used as a dispatch tool for competitive markets. In addition, the decentralized nature of competitive markets presents unique concerns for the use of OPF (which is by nature a centralized planning tool) [60].

Previous work has identified a number of desirable features for OPF programs [101, 160]. Here, we discuss these features in relation to recent industry developments:

  • High computational speed: Speed has always been a key need for practical OPF algorithms, especially in real-time applications and when dealing with very large power systems. However, competitive markets and renewable generation have reduced scheduling intervals from day-ahead blocks to hourly or sub-hourly windows. Accordingly, OPF software must now yield robust solutions in a matter of minutes. In addition, computational efficiency is necessary in order to address complex requirements such as in probabilistic OPF and security-constrained OPF, to perform iterative optimization, and to rapidly compute necessary system adjustments under emergency conditions. Finally, greater computational efficiency is required in order to incorporate the more extensive and complex models now used in the utility industry.

  • Reliability of solution: For an OPF algorithm to be used in market applications, it must be able to reliably achieve a solution for ill-conditioned problems, in outage studies, and for real-time applications.

  • Robustness of solution: OPF solutions must be insensitive to initial points and stable with respect to changes in the power system operating constraints. In particular, the algorithm must be able to handle small parameter changes that cause local infeasibility or large changes in the optimal solution point [5]. This is especially critical for real-time OPF, as it must return solutions that may be immediately applied to functioning power systems.

  • Flexibility/versatility: The algorithm must have the ability to handle both conventional and special features and must be suitable for incorporation into more complex control processes, such as energy management systems.

  • Incorporation of security constraints: The move of the electric power industry toward competitive markets has created systems where security and economic issues are more tightly interconnected than before. Because competitive markets complicate utilities’ ability to evaluate system security using pre-evaluated studies, it is vital to monitor OPF solutions for system security. The inclusion of security constraints directly within the OPF formulation therefore presents a significant advantage.

  • Discrete modeling: Modern power systems use a large number of discrete controls, such as transformer tap settings, switched capacitor banks, and branch switching. In order to assist system operators in achieving optimal use of these controls, OPF algorithms must model discrete devices in an efficient but realistic manner.

  • Incorporation of multiple objectives: Although cost is the primary objective for dispatch of generation, environmental factors now play an increasing role in choice of electricity source. The ability to simultaneously optimize multiple objectives is therefore highly desirable (for instance, minimization of both operating costs and carbon emissions).

  • Incorporation of multiple time periods: As scheduling horizons become shorter, it is desirable to optimally schedule generation across multiple time periods. Multiperiod OPF requires incorporation of generator start-up and shut-down costs, ramp rates for thermal generation, forecasting for renewable generation, and changing load conditions [4].

  • Probabilistic modeling: The use of probabilistic OPF enables analysis of the uncertainties inherent in generation price bids in competitive markets [86, 157], renewable generation, and uncertainty in future load, such as the energy consumption of plug-in hybrid electric vehicles.

  • Low storage requirements: Although computer storage is now cheap and plentiful, low storage requirements are still desirable for OPF with very large systems and in the use of computers with small core storage availability, for instance personal computers in online applications or microcomputers for distributed control.

  • Simplicity: In order to be commercially viable, OPF algorithms must be easy to understand and simple enough for rapid incorporation into energy management software.

It is very difficult to include all these features in a single algorithm, so OPF algorithms continue to be tailored for specific applications. Of these features, Wang et al. [160] state that future OPF research should emphasize algorithm robustness, accuracy, and scalability in light of the changing roles of OPF in market-oriented applications.

4 Deterministic optimization methods

In this section, we discuss the deterministic (classical) optimization methods which have been applied to OPF problems. The majority of the classical techniques discussed in the literature use one of the following methods: gradient methods, Newton’s method, the Simplex Method, Sequential Linear Programming (SLP), Sequential Quadratic Programming (SQP), and Interior Point Methods (IPMs). Here, we briefly summarize the merits of each method and discuss representative articles demonstrating how the method has been applied to OPF. In some cases, there is significant overlap among the methods. Where this is the case, we state the nature of the overlap for the reader’s reference.

4.1 Gradient methods

Gradient methods were among the first attempts to solve practical OPF problems at the end of the 1960s. Gradient methods can be divided into three lines of research: the Reduced Gradient (RG) method, Conjugate Gradient (CG) method, and Generalized Reduced Gradient (GRG) method. Gradient methods use the 1st order derivative vector ∇f(x k ) of the objective function of an NLP (that is, the gradient) to determine improving directions for the solution in iterative steps. Gradient methods are reliable, easy to implement, and guaranteed to converge for well-behaved functions. However, gradient methods are slow compared to higher-order methods. Moreover, because they do not evaluate the 2nd order derivative, they are guaranteed to find a stationary point only (which may not be a true local optimum). Global optimality can only be proven for convex optimization problems, which excludes most OPF formulations.

4.1.1 Reduced gradient method

The RG method was proposed by Wolf [163] to solve NLP problems with linear constraints. The linear constraints allow the partition of the variables into basic variables (or dependent variables) and non-basic variables (or independent variables)—a technique commonly used in LP. This allows expressing the basic variables as a linear function of the non-basic variables. The basic variables in the objective function can then be substituted by this linear relation. Maintaining feasibility of the non-basic variables is straightforward, but bounds on the basic variables and other inequality constraints must be enforced by adding indirect penalty terms to the objective function. The first derivative of this modified objective function is called the reduced gradient.

Like all gradient methods, the RG method improves the solution iteratively by moving along the direction of the reduced gradient while ensuring feasibility of the variables. Convergence is reached when the gradient becomes zero. If the KKT conditions are satisfied at this point, then it is a local optimum [46]. Although the RG method is guaranteed to converge as long as a local stationary point exists, it exhibits a well-known “zig-zag” search characteristic that slows convergence near the optimal solution.

Dommel and Tinney [45] were the first to apply the RG method to OPF, using penalty techniques to enforce the limits on the dependent variables and the functional constraints. This original work relied on 1st order information of the (nonlinear) objective and the constraints derived from the Jacobian matrix computed from a conventional power flow.

Dommel and Tinney’s work was highly influential in subsequent OPF research and foundational to the development of commercial OPF algorithms [27, 102]. Alsac and Stott [6] extended the work of Dommel and Tinney to N−1 security-constrained OPF by adding predetermined contingency cases to the power flow equations and penalizing security violations of these cases in the objective function. Fernandes et al. [47] successfully applied the RG method with penalty factors to reactive OPF. Wang et al. [161] later parallelized the RG method to make it more applicable to multi-area systems.

More recently, Jamoulle and Dupont [74] provided an overview of the historic development of RG and GRG methods for OPF in a technical report. Furthermore, the authors applied an RG method using a two-level optimization procedure that guarantees feasibility, ensures a monotonically decreasing objective, and enables near-Newton type convergence. Their method is similar to the GRG methods in that they allow variable base.

4.1.2 Conjugate gradient method

The CG method is an improvement of the RG method and is one of the most well-known iterative methods for solving NLP problems with sparse systems of linear equations. Instead of using the negative reduced gradient as the direction of steepest descent, the CG method chooses the descent direction vector as a conjugate version of successive gradients by adding the current negative gradient vector to a scaled, linear combination of previous search directions. This scalar value can be computed, for instance, with the Fletcher-Reeves method or the Polak-Ribiere method [46]. The CG method presents several advantages over the RG method. First, the search direction is always nonzero and linearly independent of all previous directions vectors, that is, the search directions are non-interfering. This helps avoid the “zig-zag” search characteristic inherent to the RG method. Furthermore, the number of steps until a solution is attained is bounded by the number of variables in the problem.

Burchett et al. demonstrated several advantages of CG for OPF, particularly the improvement in search characteristic over the RG method [18]. The authors also found that CG can be a favorable alternative to quasi-Newton approaches for problems with large reduced Hessians. The CG method has also been widely applied as the search mechanism for other, more general algorithms, such as SQP and the GRG method [19].

4.1.3 Generalized reduced gradient method

The RG method was extended by Abadie and Carpentier [1] to the GRG method to enable direct treatment of inequality and nonlinear constraints. Like the RG method, the GRG method partitions the variables into basic and non-basic variable sets. However, rather than use penalty functions, the GRG method modifies the constraints such that the required change in the basic variables can be computed directly from the non-basic variables. To accomplish this, slack variables are introduced for all inequality constraints and the constraints are linearized about the current operating point. Then, a generalized reduced gradient may be defined from the objective function that computes the total incremental change in the objective function considering both basic and non-basic variables.

The result of this operation is a series of subproblems with linear constraints; these subproblems are solved using the RG or CG method [28]. Since the linearization introduces error in the constraints, an additional step is required to modify the basic variables at the end of each iteration to recovery feasibility. In OPF, this feasibility recovery is performed by (for example) solving a conventional power flow [117]. At the final optimal solution, the approximated problem possesses the same solution as the original NLP. Vanderplaats [154] provides a good overview of the GRG method.

Peschon et al. [117] first described the application of the GRG method to OPF, clearly documenting the procedure and presenting the benefits of the GRG method. These benefits include the avoidance of penalty terms and the straightforward computation of sensitivities. Yu et al. [175] extended the GRG method to address OPF problems with tap-changing transformers and several different objective functions. Recently, de Carvalho et al. [28] combined aspects of GRG with the augmented Lagrangian and log-barrier techniques. This approach contrasts with standard GRG, where slack variables are used to eliminate the inequality constraints.

4.2 Newton’s method

Newton’s method is a 2nd order method for unconstrained optimization based on the application of a 2nd order Taylor series expansion about the current candidate solution. For a given objective function f(x), Newton’s method defines the search direction s k =−H(x k )−1∇f(x k ), where H(x k ) is the Hessian matrix of f(x) at x k . The algorithm then computes a step size α k in direction s k that yields the greatest improvement in the objective function. (For classical Newton’s method, the step is size is fixed at α k =1; this yields the exact optimum of the quadratic approximation of the objective function about x k .) Newton’s method is well-known for its quadratic convergence properties under some mild assumptions in the neighborhood of the solution [44]. However, the method is not guaranteed to converge to a local minimum unless the Hessian matrix is positive semidefinite in the vicinity of the minimum point [154].

When applied to constrained optimization (such as OPF), Newton’s method requires the use of the Lagrangian function, which includes penalty terms for the constraints. As with the gradient methods, the variables may be divided into dependent and independent variable sets to reduce the possible search directions. Limits on the independent variables are enforced directly during each move. Appropriate penalty factors for the equality constraints may be evaluated directly as part of the solution search process [164]. Inequality constraints must either be treated as equality constraints or omitted, depending on whether they are binding at the optimal solution. The active inequalities are not known prior to the solution; identification of the active inequality constraints is a major challenge for Newton-based OPF [63].

Although Dommel and Tinney recognized that the Newton’s method could be applied to OPF, they did not use it because the computational requirements were excessive at the time [45]. However, Sasson et al. [134] presented an early version of Newton-based OPF. The authors’ formulation did not use the Lagrangian but rather a series of heuristically computed penalty factors. Sun et al. [145] presented a more efficient algorithm employing the Lagrangian. The authors’ major contribution was a heuristic scheme for inequality constraint relaxation and enforcement, with the constraints enforced at their limits based on engineering judgment. This method is known as an active set and penalty (ASP) method. Hong [64] discussed the algorithmic implementation of Newton-based OPF, including numerical efficiency and ensuring algorithm stability.

A significant body of work has focused on identifying and enforcing the active inequality constraints. Maria and Findlay [94] proposed an LP approach to efficiently identify the active constraint set and also discussed methods for ensuring local convexity by modifying the Hessian matrix. Santos et al. [133] and later da Costa [38] discussed primal-dual (PD) methods which augment the Lagrangian with quadratic penalty factors. Such methods perform better in the case on non-convexity in the original Lagrangian. The challenge lies in appropriate selection and adjustment of the penalty multipliers. Crisan and Mohtadi [40] proposed an ASP technique to identify and enforce only the inequality constraints with the worst violations, thus avoiding oscillations and slow progress toward the optimal solution. However, at the optimal solution, all binding inequality constraints are enforced. da Costa et al. [39] summarized and compared three constraint enforcement methods: ASP, PD, and primal-dual logarithmic-barrier (PDLB) (an IPM). In the authors’ numerical tests, the ASP method consistently performed faster and with fewer iterations, but the solutions were usually infeasible until the local optimum is obtained.

The difficulty of enforcing inequality constraints was a motivating factor in the application of IPMs to OPF; see Sect. 4.6. However, Tognola and Bacher [148] proposed an “unlimited point” algorithm for OPF based on a penalty-factor formulation similar to that employed by IPMs, but which uses a variable transformation to eliminate the nonnegativity restrictions on the dual and slack variables. The resulting KKT conditions can be solved directly with Newton’s method without checking variable bounds. Taking a different approach, Adibi et al. [3] applied a modified, barrier-augmented Lagrangian (MBAL) method to the problem of optimizing transformer tap settings, arguing that the MBAL method is more robust than IPMs.

4.2.1 Quasi-Newton methods

A major disadvantage of Newton’s method is that the calculation and inversion of the Hessian matrix is very computationally intensive. This has inspired the development of various quasi-Newton methods: methods which approximate the Hessian matrix using various efficient algorithms. In some cases, quasi-Newton methods can be significantly faster than the full Newton’s method; in others the performance is poor because the approximate Hessian matrix fails to indicate efficient search directions. Nocedal and Wright [108] contains additional information on quasi-Newton methods.

Housos and Irisarri [66] discussed the performance the two most common quasi-Newton methods—the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and Davidon-Fletcher-Powell (DFP) method—with respect to OPF. The authors concluded that, if combined with appropriate heuristic controls, these methods can effectively solve the classical OPF problem. Additionally, quasi-Newton methods were used as the local solver in some early SQP algorithms for OPF [19]. However, in recent years quasi-Newton methods have not received much attention because the Hessian matrix of most OPF formulations is not difficult to develop analytically and matrix manipulation techniques have reduced the computational difficulties associated with matrix inversion.

4.3 Simplex method

The Simplex Method is perhaps the oldest and most robust formal optimization method for LP. The Simplex Method exploits the convexity of linear programs (both in the objective and the constraint set) by systematically exploring the vertices of the feasible region until no further improvement to the objective function is possible. Although in theory the Simplex Method is (in the worst case) an exponential time algorithm [80], in practice, the Simplex Method performs extremely well for most LP problems [136].

The Simplex Method may be applied directly to DC-OPF formulations, and has also been applied to incremental linear models of power systems. Incremental models seek to optimize operation via small changes around a base point, and are therefore well suited for online OPF. The simplest of these algorithms apply a single linearization only and seek a local optimal solution. Stott and Hobson [140] provide an excellent discussion of DC-OPF vs. OPF using incremental linear models. Stott and Marinho [141] is a useful example: the authors used incremental LP models to alleviate line overloads and perform security-constrained economic dispatch (SCED) of generation. The Simplex Method is also the solver used for many SLP algorithms for OPF.

4.4 Sequential linear programming

The majority of LP-based OPF algorithms in the published literature do not use a single linearization. Rather, they implement a form of Sequential Linear Programming (SLP), also known as Successive Linear Programming. SLP is an extension of LP introduced by Griffith and Stewart [58] that allows the optimization of problems with nonlinear characteristics via a series of linear approximations. The original NLP is reduced to an LP using a linear approximation of the objective function and constraints about an initial estimate of the optimal solution. The resulting LP is then solved, a new linearization is performed about the new solution point, and the process repeats until convergence [17, 179]. The solver selected is typically a variant of the Simplex Method or an IPM; papers combining SLP with IPM are discussed in Sect. 4.6.

SLP handles all types of continuous constraints easily and provides speed, flexibility, and accuracy for specific applications. SLP methods with only a few binding constraints in the solution have simple, rapid initialization and can detect infeasibility at an early stage of the optimization process [42]. A major weakness of SLP is that it cannot find an optimum for NLPs in which the linearization yields an unconstrained search direction. This can be overcome by using the concept of a “trust region” to which the LP search is restricted [13].

In SLP as applied to OPF, an optimal solution is obtained by iterating between conventional power flow and linearized LP subproblems [187]. Specifically, at each iteration the linearization is performed by generating a 1st order Taylor series expansion about the solution of a conventional power flow. SLP is desirable for OPF because it retains the speed of LP but approaches the accuracy of NLP methods. In addition, SLP can guarantee improvement in the objective function at every iteration [7]. However, because the linear program is constructed around a current operating point, these methods find local optima only. In addition, the linearization process can lead to oscillation as the algorithm approaches the optimum [127], or to slow convergence and even divergence in the case of highly nonlinear objective functions [62].

Mota-Palomino and Quintana [105] applied SLP to reactive power dispatch using a penalty-factor LP technique, placing an emphasis on algorithm performance. Kirschen and Meeteren [79] presented a novel SLP technique allowing the rescheduling of active power controls to correct voltage magnitude problems even when using a decoupled optimization approach. Alsac et al. [7] describe a general framework for applying SLP to a wide variety of OPF problems. The authors report that their approach has been successfully implemented in commercial OPF software and yields the same results as Newton and gradient methods for power systems of any size and type.

SLP has also been used for reactive power planning. Iba et al. [68] discussed convergence and numerical performance issues related to using SLP for reactive power planning. Thomas et al. [146] applied a heuristic method for optimizing security-constrained reactive power planning by solving a series of single state reactive power cost minimization problems with SLP. Yehia et al. [174] proposed a trade-off methodology for solving reactive power compensation problems considering both technical and economic objectives. The authors used SLP to solve the individual optimization problems, linearizing the system with respect to the current voltage magnitudes.

More recently, Zehar and Sayah [178] used SLP to solve a multi-objective OPF, minimizing generation costs and emissions. The authors used a variable weighting factor to accommodate the two objectives in a single function. The authors’ use a fixed size trust region limiting the maximum deviation of the decision variables from the current operating points. This approach reduces error between the LP subproblem and the original NLP, but also slows solution progress.

4.5 Sequential quadratic programming

Sequential Quadratic Programming (SQP), also known as Successive Quadratic Programming, is the solution of an NLP problem by solving a series of QP problems that converge to the optimal solution of the original problem [13, 14]. In this way, SQP is similar to SLP. At each iteration, the algorithm generates a quadratic program that approximates the behavior of the NLP problem about a particular operating point (typically, the optimal solution from the previous QP iteration). Next, the QP subproblem is solved to optimality. The optimal solution of the QP subproblem then forms the starting point for the next SQP iteration, and the process is iterated to convergence. SQP can be significantly more efficient than general NLP approaches and has been successfully applied in a number of research and commercial OPF algorithms. However, like SLP, SQP can suffer from oscillations when nearing the optimal solution [127].

In nearly all SQP implementations for OPF, conventional power flow is used to linearize the constraints at each iteration, then a deterministic optimization method is used to solve the resulting QP. The use of conventional power flow to perform the linearization increases computational efficiency. In the implementation of Burchett et al. [19, 20], a gradient method combined with Simplex Method-like iterations provides the solution for the QP subproblems. The SQP procedure described in Contaxis et al. [37] is similar, but the authors do not specify with NLP optimization method is used to solve the QP subproblems. For loss minimization, Chang et al. [30] presented a practical application of SQP using Newton’s method, introducing several heuristic techniques to improve algorithm performance.

Grudinin extended earlier SQP work by formulating a quadratic-separable algorithm for SCED and a QP algorithm for reactive power optimization [61, 62]. Both papers discuss the use of multiple objectives via proportional weighting of objective functions. Lehmköster [84] applied SQP to cost minimization, incorporating control of FACTS devices and market constraints. Lin et al. [91] applied SQP to a reactive power cost minimization problem while incorporating a minimum voltage stability margin constraint. The main contribution of these papers is the description and development of new OPF constraints and objectives suitable for use with SQP.

Other authors have proposed modifications to SQP to accommodate specific OPF problem characteristics, specifically nonconvexity. Granelli and Montagna [56] introduced two modifications to an SCED SQP algorithm: the use of a diagonal approximation of the Hessian matrix of the QP subproblems in order to ensure convexity and the addition of algorithmic steps designed to rapidly detect infeasibility. In order to ensure convexity in the QP subproblems, Berizzi et al. [15] used the Han-Powell method (a modification of SQP) to solve an SCED problem incorporating the control of FACTS devices.

4.6 Interior point methods

Interior Point Methods (IPMs) are a family of projective scaling algorithms for solving linear and nonlinear optimization problems that constrain the search to the feasible region by introducing barrier terms to the objective function. In general, IPMs attempt to determine and follow a central path through the feasible region to the optimal solution. The first IPM was introduced by Karmarkar [77] as a replacement for the Simplex Method for LP. Karmarkar’s work was later refined by many other researchers, and IPMs have been shown to be highly competitive with the Simplex Method, especially for large problems, degenerate linear programs, and stochastic programs. For linear programs, IPMs approach the boundary (and therefore the optimal solution) only in the limit and require significantly more complex computations at each iteration than the Simplex Method [108]. However, IPMs also achieve superior progress at each iteration, greatly reducing the number of iterations and often reducing the total solution time as well. IPMs have a pseudo-polynomial bound on the worse-case running time that is better than ellipsoid algorithms [59]; such a bound is not known for the Simplex Method.

Spurred by the success of IPMs for LP, researchers have extended IPMs to NLP problems. When applied to NLP, IPMs use a variant of Newton’s method to simultaneously solve for the decision variables, slack variables, and appropriate values of the Lagrange multipliers to ensure that the KKT conditions are met at the optimal solution point [108]. A key feature of IPMs is the enforcement of feasibility, either using (typically logarithmic) barrier terms in the augmented objective function or by directly manipulating the required KKT conditions. (If an algorithm starts at an infeasible point, artificial variables may be used to regain feasibility until a strictly feasible point for the original constraint set is found.) Modern IPMs present three appealing characteristics: ease of handling inequality constraints through the use of barrier functions, rapid convergence, and the ability to solve a problem without starting from a strictly feasible initial point [23, 57, 166].

The earliest application of IPMs to OPF was the use of linear IPMs to replace the Simplex Method as the optimization algorithm used for SLP-based OPF. Motivated by Karmarkar’s work, both Vargas et al. [156] and Lu and Unum [93] solved an SCED problem using SLP and the dual affine IPM for linear programming. Momoh et al. [100] extended Karmarkar’s algorithm to SQP and applied it to reactive power planning. Later, Momoh and Zhu [99] further improved the same algorithm; Zhu [189] provides an excellent summary of the resulting method.

In the OPF literature, several enhancements over earlier IPMs have now achieved popularity, including Primal-Dual Interior Point Methods (PDIPMs) [57], Mehrotra’s predictor-corrector (PC) techniques [70, 150, 162], Gondizio’s multiple-centrality corrections (MCC) PDIPM [23, 152], and trust region techniques [78, 97]. Castronuovo et al. [29] compared the numerical performance of several of these methods.

4.6.1 Primal-Dual interior point methods

Primal-Dual Interior Point Methods (PDIPMs) are a class of IPMs that directly solve for the primal, dual, and slack variables of a linear or nonlinear program as it approaches optimality. To relate the variables, PDIPMs formulate a set of nonlinear equations representing the KKT conditions of the barrier augmented Lagrangian function for the optimization problem given a heuristic barrier parameter μ, or (equivalently) a set of “perturbed” KKT conditions for the unaugmented Lagrangian given a heuristic complementarity parameter μ [108]. μ may be fixed or updated dynamically as the algorithm progresses, yielding a wide variety of PDIPM algorithms. In practice, μ governs the balance between algorithmic progress toward a reduced objective function value and adherence to the central path of the feasible region. By proper selection of μ, PDIPMs can ensure that long steps toward optimality are possible at each iteration, reducing the total number of required iterations. However, finding the proper selection and update procedure for μ is a key challenge. Since the solution at each iteration must remain feasible with respect to the problem dual variables and slacks, an improperly selected μ can yield a search direction which drastically shortens Newton step lengths [22]. Further technical discussion of PDIPMs may be found in Wright [165] and Nocedal and Wright [108].

PDIPMs have demonstrated excellent performance in solving many OPF problem variants, including SCED, reactive power dispatch, determination of the stability margin, and reactive power planning. PDIPMs are perhaps the most popular deterministic algorithm discussed in recent OPF research. Granville [57] pioneered the application of PDIPMs to the OPF problem, extending earlier PDIPMs for LP and QP to the NLP case of the reactive power dispatch problem. Granville observed that the PDIPM offered several key advantages over earlier Newton approaches, including no requirement to identify the active constraint set and no requirement to have an initial feasible solution.

Granville’s work inspired a great deal of research, some of which has focused on improving the performance of PDIPMs with respect to the unique nature of power flow constraints. Vanti et al. [155] proposed a modified PDIPM which uses a merit function to enhance the convergence properties of earlier PDIPMs for OPF. The merit function allows a modification of search direction when progress from the Newton steps is poor. Zhang et al. [183] contributed a simplified OPF formulation using rectangular coordinates and current mismatches. The authors report that the resulting simplifications to the Hessian matrix reduce computational effort and yield simpler computer code. Qiu et al. [118] parallelized a PDIPM for security-constrained OPF by using a transformed problem structure with a block diagonal matrix representation of the Newton update equations, allowing considerable speedup. Bai and Wei [11] proposed an MINLP model for SCUC by using semi-definite programming (SDP) and solved it using a specialized PDIPM. The primary advantage of using SDP is that a solution can be obtained in polynomial run time.

Other research has focused on the application of PDIPMs to various types of OPF problems. Several authors have used PDIPMs to address power system loadability. Parker et al. [115] applied a PDIPM with a fixed 1/x type barrier parameter to determine the reactive power margin of a transmission system, reporting that the PDIPM was more reliable than active-set methods. Both Irisarri et al. [69] and Dai et al. [41] applied PDIPMs to calculate the maximum loadability of a power system. A key contribution of Dai et al. is the discussion of the impact of barrier parameter selection on algorithmic oscillations near the boundary of the feasible region.

PDIPM approaches have been extended to include complex control elements. For instance, Zhang et al. used PDIPM as the solution algorithm for a general OPF formulation that incorporates models for Unified Power Flow Controllers (UPFCs) [182, 185]. de Oliveira et al. [111] used a PDIPM as the local solver within an iterative method to determine optimal switch states for a radial distribution system.

4.6.2 Predictor-Corrector PDIPM

Mehrotra introduced predictor-corrector (PC) techniques for PDIPMs as a method for improving the search direction at each iteration [96]. Mehrotra’s 2nd order PC-PDIPM uses a two-step process at each iteration: a prediction and a correction. The prediction step searches in the affine-scaling direction, that is, the Newton direction that (neglecting the bounds on the decision variables) provides the greatest improvement to optimality. Subsequently, the correction step dynamically estimates the proper value for the barrier parameter μ and restores centrality to the solution. This approach is often more efficient both computationally and in number of iterations than conventional PDIPMs [132].

Mehrotra’s technique was developed for LP, and both Yan and Quintana [173] and Xiao et al. [169] employed PC-PDIPMs for LP as the solver for SLP-based OPF; Xiao et al. also introduced an OPF model for FACTS devices. However, much more research has been dedicated to extending Mehrotra’s technique to NLP. PC-PDIPM has been implemented with considerable success for nonlinear OPF, including for large scale problems.

Wu et al. [166], Irisarri et al. [69], and Torres and Quintana [150] all compared conventional PDIPM with PC-PDIPM. The work of Wu et al. established the attractive convergence and speed characteristics of PC-PDIPM over PDIPM and also discussed a number of practical considerations. Irisarri et al. calculated maximum system loadability while Torres and Quintana optimized transmission losses; both sets of authors concluded that PC-PDIPM has considerable potential to improve the performance of practical OPF algorithms. Similarly, Garzillo et al.[51] reported approximately 20 % savings in calculation time through use of PC-PDIPM over conventional PDIPM for several active and reactive power dispatch test cases. Wei et al. [162] reported a 15 % improvement in CPU time and a 50 % improvement in storage requirements over conventional PDIPM via the use of a PC-PDIPM with an efficient, novel data structure.

Most recent papers on PC-PDIPMs for OPF focus on improvements to increase algorithmic efficiency and the development of effective models for complex system controls. Jabr et al. [73] described a step length filter to improve convergence. Jabr [70] then compared a symmetric PC-PDIPM with the earlier asymmetric approaches of Torres and Quintana and Wei et al. In particular, Jabr investigated practical performance issues, such as stopping criteria, the selection of a good starting point, and how to ensure local convexity at the solution. In the area of controls modeling, Yan et al. [172] introduced a tap-changing transformer model that retains the quadratic nature of OPF in rectangular coordinates, hence retaining constant Hessian matrices. Thus, the Hessian needs to be calculated only once, increasing the efficiency of PC-PDIPM iterations. Jabr [71] used a variable transformation to model the OPF problem in extended conic-quadratic (ECQ) format, which linearizes some of the power injection equations and simplifies several constraints. The resulting problem is solved via a PC-PDIPM. Jabr reported that the ECQ-OPF also allows efficient representation of both regulating transformers (including phase shifters) and UPFC devices.

Lin et al. [90] reformulated the OPF problem using a hybrid equivalent current injection approach, reporting that the resulting problem has smaller storage requirements and may be solved faster by PC-PDIPM. Azevedo et al. [9] took a different approach, using a network flow model instead of OPF in polar or rectangular coordinates. The authors reported that FACTS devices can be included in the model without significantly increasing computational requirements and that PC-PDIPM was able to solve the formulation quickly and reliably for several large test cases.

Two papers have addressed cases where infeasibility or poor starting conditions can cause PC-PDIPM to diverge. Chiang et al. [33] developed a two-step algorithm: the first step finds a feasible solution as a starting point, and the second step applies PC-PDIPM to find a local optimum. The authors reported that their algorithm converges in several cases where PC-PDIPM alone diverges. Moyano and Salgado [106] observed that in some cases, PC-PDIPM based OPF fails to converge because there is no feasible solution. They describe a procedure for relaxing the demand constraints such that the PC-PDIPM algorithm can still converge even in the case of infeasibility. The relaxation technique has little effect on algorithm efficiency and does not alter the optimal solution if the original problem is feasible.

4.6.3 Multiple centrality corrections PDIPM

The success of PC-PDIPM led to research into the use of multiple corrections during each PC-PDIPM iteration in order to achieve the best possible step direction [25]. Among multiple correction methods, Gondzio’s Multiple Centrality Corrections (MCC) approach is one of the most efficient and widely implemented [55]. Gondzio observed that in practice Mehrotra’s PC-PDIPM method fails to make significant progress in cases when some of the complementarity products of the primal and dual variables differ by several orders of magnitude. In such cases, the iteration is badly centered. To address these cases, Gondzio proposed a heuristic method which first solves for the affine scaling direction, and then subsequently modifies this direction repeatedly to reduce the difference in complementarity products after the proposed step (thereby improving the centrality of the next iteration). The correction procedure makes use of the same Jacobian matrix as the prediction procedure, and therefore adds minimal computational burden. The correction may be repeated any number of times, but in practice is terminated after a set number of corrections or when the incremental improvement to centrality becomes small. Use of the MCC method at each iteration ensures that step lengths remain long, accelerating algorithm convergence.

As with PC-PDIPM, MCC-PDIPM was originally developed for LP but has been extended to NLP-based OPF. Torres and Quintana [152] describe in detail the application of MCC-PDIPM to NLP in general and a complex OPF formulation in particular. The authors observe that the PC-PDIPM and MCC-PDIPM algorithms are able to solve some difficult cases where regular PDIPM fails and also that MCC-PDIPM consistently performs more efficiently than PC-PDIPM. Similarly, Capitanescu et al. evaluated MCC-PDIPM for OPF and compared it to other PDIPM methods [22, 23]. The authors’ results show that MCC-PDIPM typically reduces total iterations compared to PC-PDIPM and is competitive in overall computation time as well, especially for highly nonlinear formulations.

Rider et al. [126] proposed an efficient method for computing the optimal step size for the primal and dual variables as part of each MCC-PDIPM iteration. Later, Rider et al. [125] made some further modifications to MCC-PDIPM by combining certain aspects of previous PC-PDIPM and MCC-PDIPM algorithms, reporting slightly improved performance compared to Gondzio’s original approach. Capitanescu et al. [24] applied MCC-PDIPM to an MINLP OPF problem where integrality constraints are enforced via the use of nonlinear equilibrium constraints. The authors compared various methods of constraint enforcement and their impact on the algorithm’s numerical stability.

4.6.4 Trust region interior point methods

Deterministic optimization methods in general perform an iterative search of the solution space by forming an approximation of the problem at each iteration and using it to define both a search direction and a new trial point. Trust region methods introduce the concept of quality to the local approximation: the approximate model at each iteration is only trusted within a locally bounded region, called the trust region. Thus, trust region methods limit the search at each iteration. By dynamically restricting the search to the region where the approximation is good, trust region methods can mitigate the effects of problem nonlinearity, nonconvexity, and ill-conditioning [176].

Trust region interior point methods (TRIPMs) consist of a trust region method combined with any of the IPM techniques discussed above. As applied to OPF, TRIPMs have been primarily used in combination with SLP and SQP. Min and Shengsong [97] applied a trust region MCC-PDIPM to SLP-based OPF by using a ratio test between predicted and actual merit function improvement. Sousa et al. [138, 139] demonstrated a two-part, SQP-based TRIPM designed to facilitate convergence for very difficult OPF problem cases, demonstrating that the TRIPM converged in cases where other PDIPM algorithms failed. The papers document a practical illustration of the global convergence properties of the TRIPM, rather than a formal proof. Karoui et al. [78] applied the KNITRO IPM software to an SCED problem, noting its use of a trust region to control direction and step length.

Step-controlled IPM (SCIPM) is another convergence-enhancing method similar to TRIPM. SCIPMs restrict step length not based on an explicit trust region but rather by monitoring solution accuracy along the search vector. Wang et al. [159, 160] compared a TRIPM to SCIPM for the case of discrete market price points. Such pricing jumps cause convergence difficulties for standard PDIPMs, but the authors found that both a TRIPM and a SCIPM were able to solve the OPF. The authors concluded that in practice, the SCIPM is superior due to its computational efficiency.

4.7 Additional methods

Benders’ decomposition

Yamin et al. [171] applied Benders’ decomposition towards a dynamic OPF problem. The transmission security constraints are checked by solving Bender’s subproblems; a Benders’ cut is passed to the Master Problem when the transmission security constraints are violated. A linearized model for the transmission security constraints is proposed. This leads to a globally convergent algorithm because the subproblems are LPs.

Li and McCalley [87] proposed a risk-based optimal power flow problem, which minimizes operational cost considering the system’s reliability. A risk index is used to quantify the risk associated with system’s operation decisions. The authors proposed a Benders’ Decomposition algorithm where the Master Problem is an OPF problem and the subproblems implement the risk exposure following three different stages: (1) for each contingency scenario, a feasibility problem is solved to check for the possibility of a corrective control; for each non-satisfiable contingency, a Benders’ feasibility cut is generated, (2) for each contingency scenario, a Benders’ feasibility cut is generated if there is a possibility for a collapse or cascading overload, and (3) a risk minimization model passes Benders’ optimality cuts to the Master Problem.

Generalized Benders’ decomposition

Alguacil and Conejo [4] proposed a Generalized Benders’ Decomposition technique to solve a unit commitment problem with DC-power flow equations. The unit commitment decisions are decoupled from the OPF problem, resulting in MILP master problems and continuous, nonlinear subproblems. Feasibility and optimality cuts are iteratively generated and convergence of the algorithm is established.

General decomposition

Conejo et al. [36] developed a general decomposition method tailored to large-scale linear and nonlinear programming problems where complicating constraints are treated by a modified Lagrangian relaxation technique. The idea of Lagrangian relaxation is to move troublesome constraints into the objective function by penalizing their violation via so-called Lagrangian multipliers; this leads to a decomposition of easier to solve problems. In contrast to standard Lagrangian relaxation, the procedure of Conejo et al. allows for automatic updates of the Lagrangian multipliers. Furthermore, approximate Newton direction in combination with the conjugate gradient method ensure local convergence under mild conditions. The authors apply their algorithm towards a multi-area OPF problem, where the coupling constraints of flow between different areas are the complicating constraints; more details can be found in [109].

Nonlinear complementarity

Nonlinear complementarity (NC) algorithms use a penalty formulation very similar to IPMs but modify the system of equations such that the variables are not sign restricted. As a result, there is no need to enforce nonnegativity during the iterative search process. Torres and Quintana [151] presented an NC algorithm for OPF and compared its performance with several PDIPM variants. Because of the similarity of the NC algorithm to IPM, the authors note that both could be incorporated into the same OPF software. The authors later improved their algorithm by introducing a Jacobian smoothing technique to improve the search directions [153]. Building upon Torres and Quintana’s work, Patra and Goswamib [116] presented a predictor-corrector NC algorithm where the smoothing parameter is included as a variable and updated in each iteration.

Semi-infinite programming

Xia and Chan [168] modeled a dynamic constrained OPF problem using semi-infinite programming techniques; i.e., finiteness in the number of decision variables is maintained while a continuum of (infinitely many) constraints are required. The dynamic component is added to ensure reachability of a steady-state operation even after specific contingencies are observed. The authors transformed the semi-infinite programming problem to a regular NLP using a local reduction method.

Tie-line decomposition

Bakirtzis and Biskas [12] considered a DC-OPF problem with quadratic cost function, proposing a decomposition of the linearly constrained QP by different utility control areas. The decomposed problem is solved iteratively by passing dual information on the tie-line power flows. Their algorithm converges to an optimal solution of the original QP.

Sequential MILP

Lobato et al. [92] proposed a sequential piece-wise linear MILP algorithm for a linearized OPF problem with convex quadratic cost functions. The authors modeled shunt reactors and capacitors with integer variables while the quadratic costs are given by the generator reactive margins. Their algorithm generates iteratively linear underestimator functions on the true quadratic cost function by solving MILP problems.

5 Summary of deterministic optimization methods

As part I of a two-part survey of optimization methods for OPF, this article has examined the various deterministic optimization methods that have been applied to the OPF problem. Significant progress has been made in solving the OPF problem, both in theoretical terms and in practical algorithms. The seminal works by Carpentier [26] and Dommel and Tinney [45] introduced both the classic NLP formulation for OPF and gradient methods by which to solve it. Important contributions since that time include incremental linearization techniques and the use of SLP methods [140]; the application of SQP techniques to improve solution speed of the classic NLP formulation [19]; the development of ASP techniques to enforce nonlinear constraints and the accompanying use of Newton’s method [145]; and the application of nonlinear IPMs to the OPF problem [57]. In general, key developments in the OPF formulation have been accompanied by developments in solution techniques. Moreover, the application of new solution techniques has paralleled increases in computing ability such that recent OPF algorithms are much more computationally intensive than the original gradient methods.

Table 4 summarizes the major deterministic methods discussed in this survey. The first table column lists the methods while the second column gives the types of formulations that have been used with the method. The third table column provides one or two references which we consider as a good starting point for novices to this methodology. In selecting these references, we have attempted to choose papers that provide a clear and concise explanation of the method and its application to OPF. The fourth column indicates whether the method is globally convergent for OPF problems; this is discussed in more detail below. Finally, the last column provides commentary that allows a brief comparison of the advantages and disadvantages of the various methods.

Table 4 Comparison of deterministic techniques
Full size table

In the fourth table column, we indicate whether the algorithm is globally convergent with respect to typical OPF formulations of the type indicated in the second table column, that is, whether the algorithm is known to always find a solution for well-behaved OPF formulations regardless of the initial starting point. (Problem feasibility and appropriate parameter selection are assumed.) While we feel that this column provides useful information, there are several important caveats:

  1. 1.

    The applicability of the global convergence pronouncement is limited to OPF formulations, which are non-convex. Thus, several methods which are globally convergent for convex formulations only (notably, Newton-type methods) are marked with a “no” in the table.

  2. 2.

    A “yes” does not indicate that solution found will be globally optimal; none of the deterministic methods described in the table can guarantee global optimality for OPF problems.

  3. 3.

    Many of the methods discussed in the table may be made globally convergent through the use of trust-region techniques or other algorithmic modifications [108]. However, the use of such techniques often undermines the efficiency of the underlying algorithms.

We refer the interested reader to Nocedal and Wright [108] for additional discussion and references regarding the convergence of these methods, including proofs of convergence for those algorithms marked “yes” for global convergence.

At present, the most powerful deterministic algorithms for OPF are active-set SLP and SQP methods and variants of PDIPMs. These methods exhibit both the fastest execution times and most accurate handling of nonlinearity. However, each deterministic approach has its own advantages and disadvantages. The early gradient methods accurately represented the NLP problem structure, but their computational performance is poor compared to newer methods. LP and SLP methods are fast and highly reliable, but require linearization of the underlying OPF formulation. Inaccuracies introduced by this linearization can sometimes cause the problem to become unbounded or to converge to a suboptimal solution, and the successive linearization process can itself be time consuming. SQP methods improve on SLP by allowing a more accurate representation of the objective function, but still suffer from linearization issues for the constraints. In addition, SLP, SQP, and early Newton methods are all active-set methods, that is, they require the identification of the active set of inequality constraints at each iteration. This is a key challenge which reduces the efficiency of active-set methods for tightly constrained problems. PDIPMs variants, including PC-PDIPM and MCC-PDIPM, are the fastest deterministic OPF methods currently known. However, they suffer from reliability concerns, particularly algorithm divergence in certain difficult cases. Moreover, all the NLP methods have difficulty recognizing problem infeasibility.

Finally, the deterministic methods surveyed suffer from two common shortcomings:

  • All are local solvers only: they cannot guarantee global optimality except in the case of a convex problem; this is because the KKT conditions are not sufficient for a global optimum in general. Since the OPF problem is inherently non-convex, multiple local optima may exist. This issue has long been recognized, although in practice the various deterministic methods tend to converge to the same optimal solution in any given problem [114].

  • The majority are continuous solvers: they cannot readily handle binary or integer variables. As a result, switching controls in the power system cannot be accurately modeled. This limits the scope of OPF problems that may be effectively solved with deterministic solvers.

These two shortcomings have motivated significant work in the area of non-deterministic, that is, heuristic, optimization methods for OPF, including methods that hybridize multiple approaches. We refer the reader to part II of this survey, Frank et al. [49], for a discussion of these heuristic and hybrid optimization methods and for the survey conclusions.