(621f) Strengthened Socp Relaxation and Efficient Hybrid Bounds Tightening Scheme for the Global Solution of AC Optimal Power Flow Problems

The alternating current optimal power flow (ACOPF) problem is a nonconvex optimization problem that models the steady-state physics of AC power grids and is fundamentally important for grid operations at all scales, including short-term generator dispatching, day-ahead unit commitment, and long term network design and expansion planning. Unfortunately, due to the size and complexity of the ACOPF problem for realistic power networks, grid operations today are much more commonly based on linear approximations of the ACOPF model, resulting in solutions that are (after some postprocessing) feasible but potentially highly suboptimal for ACOPF. However, the Energy Information Agency estimates that improving the quality of ACOPF solutions by just 1% could save 6 billion dollars annually in US electricity markets alone.

Existing algorithms for solving ACOPF can be roughly categorized into three groups: local methods, convex relaxation methods, and global methods. Local methods aim to find a local solution or stationary point of ACOPF, but provide no guarantee of solution quality since ACOPF is a highly nonconvex problem. Interior point methods and Newton-Raphson algorithms are the most popular local solution strategies for ACOPF. In contrast, convex relaxation methods aim to find a lower bound on the global solution of ACOPF by solving a single convex relaxation, typically in the form of a semidefinite program (SDP), a second-order cone program (SOCP), or a quadratic program (QCQP). Although these methods are not guaranteed to produce even feasible solutions, they have drawn a lot of attention because these relaxations are provably exact in some cases. Moreover, it is possible to test for exactness of the relaxations in general once the relaxation has been solved, and it has been shown that they are often exact in practice, leading to a global solution at relatively low cost. However, when the relaxation is not exact, the resulting solution has no useful physical meaning and cannot be implemented. Finally, global methods aim to obtain a guaranteed global solution of ACOPF using spatial branch-and-bound methods or nonconvex outer-approximation with piece-wise convex relaxations. These methods also make use of SDP relaxations, SOCP relaxations, or more general QCQP relaxations. The key challenge for global methods is that industrially relevant ACOPF problems involve tens of thousands of optimization variables, making exhaustive branching procedures impractical in most cases. In state-of-the-art global ACOPF methods, domain reduction based on optimization-based bounds tightening (OBBT) plays a central role in mitigating this problem and ultimately closing the optimality gap for many nontrivial problems with minimal or no branching. However, OBBT can be very costly as well because it requires the solution of two convex relaxations of the original problem per decision variable in each iteration of the bounds tightening scheme.

To address these challenges, this talk presents a strengthened SOCP relaxation based on McCormick envelopes of bilinear terms, cycle basis relaxations by using piecewise linear arctan relaxations without integer variables, and so-called reverse cone cuts that are added dynamically in order to obtain a tight relaxation while keeping the model as concise as possible. We also propose an efficient hybrid bounds tightening to reduce the computational cost of OBBT. We first identify a minimal subset of the variables such that performing OBBT on only these variables is equivalent or nearly equivalent to performing OBBT on the entire set of decision variables. Next, we utilize simple bound updates based on interval arithmetic (IA) to replace a large number of the optimization problems that must be solved in straightforward implementations of OBBT. This reduces the computational cost, but also takes advantage of nonconvex constraints in a manner that cannot be done with conventional OBBT because each OBBT update is based on a convex relaxation. We also introduce a new multivariate interval arithmetic-based bounds tightening step based on the geometry of voltage angle-magnitude pairs for every generator, each of which lies in a nonconvex donut-like region. Finally, we develop an efficient hybrid BT scheme incorporating all of these elements that achieves high efficiency without losing the effectiveness of conventional OBBT.

The advantages of our proposed method will be demonstrated through extensive tests using a challenging set of NESTA benchmark problems.