Accurate and Warm-Startable Linear Cutting-Plane Relaxations for ACOPF

We present a linear cutting-plane relaxation approach that rapidly proves tight lower bounds for the Alternating Current Optimal Power FlowProblem (ACOPF). Our method leverages outer-envelope linear cuts for well-known second-order cone relaxations for ACOPF along with modern cut management techniques. These techniques prove effective on a broad family of ACOPF instances, including the largest ones publicly available, quickly and robustly yielding sharp bounds. Our primary focus concerns the (frequent) case where an ACOPF instance is considered following a small or moderate change in problem data, e.g., load changes and generator or branch shut-offs. We provide significant computational evidence that the cuts computed on the prior instance provide an effective warm-start for our algorithm.

I. Introduction

The Alternating-Current Optimal Power Flow (ACOPF) problem [1] is a well-known challenging computational task. It is nonlinear, non-convex and with feasible region that may be disconnected; see [2], [3]. From a theoretical perspective, in [4], [5] it is shown that the feasibility problemis strongly NP-hard; [6] proved that it is weakly NP-hard on starnetworks. In the current state-of-the-art, some interior point methods are empirically successful at computing excellent solutions but cannot provide any bounds on solution quality.