Title: Global Optimization Methods for Optimal Power Flow and Transmission Switching Problems in Electric Power Systems

Advisors: Dr. Santanu S. Dey, Dr. Andy Sun

Committee members: Dr. Shabbir Ahmed, Dr. Natashia Boland, Dr. Daniel Bienstock (Columbia University, Department of Industrial Engineering and Operations Research)

Location: Groseclose 402

Date: Thursday, June 30

Time: TBD

Summary: Power engineering is concerned with the generation, transmission, and distribution of electricity over electric power network. In this thesis, we  focus on two operational level optimization problems from power system planning, namely the Optimal Power Flow Problem (OPF) and the Optimal Transmission Switching (OTS) Problem. The former is a nonlinear network problem and the latter is the network design version of the first one. Due to nonlinearity induced by alternating current power flow equations, these two optimization problems, defined precisely in Chapter 1, are nonconvex and require efficient global optimization methods.

In Chapter 2, we consider Alternating Current OPF (AC OPF) problem over radial networks and analyze the approximation outcomes of  the semidefinite programming (SDP) relaxation, which  is proven to be exact over radial networks under some technical conditions.  We design a library of instances that demonstrate  positive SDP optimality gaps when these conditions do not hold. Finally, we propose valid inequalities and variable bound tightening techniques that significantly improve the computational performance of a global optimization solver.

Our work demonstrates the need of developing efficient global optimization methods  for the solution of OPF even in the simple but fundamental case of radial networks.

In Chapter 3, we focus on the solution of AC OPF problem for the general case of meshed networks. This chapter proposes three strong second-order cone programming (SOCP) relaxations for the AC OPF problem by exploiting the underlying network structure.  Two of these three relaxations are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in the literature  in terms of both quality of the relaxations and practicability to obtain feasible solutions within a time framework that is compatible with the real-time operations in the current industry practice.

In Chapter 4, we again consider the AC OPF problem with a particular emphasis on solving more challenging instances. We analyze the properties of the minors and submatrices of the matrix variable in a lifted formulation, and obtain a stronger SOCP relaxation than the ones proposed in Chapter 3 by the addition of valid inequalities and improved bound tightening techniques. We also propose an SOCP based spatial branch-and-cut algorithm to solve the most difficult instances. Overall, our methodology provides a computationally tractable approach to obtain strong relaxation bounds for some of the hardest OPF instances from the literature.

In Chapter 5, we consider the so-called Direct Current OTS problem, which incorporates  a linear approximation to nonconvex AC power flow equations. Most research on DC OTS has focused on heuristic algorithms for generating quality solutions. However, the mathematical theory of the DC OTS problem is less well-developed.  In this chapter, we formally establish that DC OTS is NP-Hard.  We characterize the convex hull of a cycle-induced relaxation inspired by Kirchoff's Voltage Law, and this characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC OTS.   We give details of a practical implementation, and show promising computational results on standard benchmark instances.

In Chapter 6, we focus on the OTS problem with the full AC power flow model  since the commonly-used DC approximation of the power flow model is known to result in  inaccurate flow solutions.  In this chapter, we propose  a new exact formulation for AC OTS and its mixed-integer second-order cone programming (MISOCP) relaxation. We improve this relaxation via several types of strong valid inequalities inspired by the developments for the  AC OPF problem in Chapter 3. We also propose a practical algorithm to obtain high quality feasible solutions for the AC OTS problem. Extensive computational experiments show that the proposed formulation and algorithms  lead to significant cost benefits with provably tight bounds.