Polar Branch-and-Bound Algorithm for Global Non-Convex Optimization in Energy Networks

Project Overview

This work seeks to address two recurrent needs in energy networks: (i) determining whether a network can function under a given (possibly degraded) configuration (feasibility problem) and (ii) finding cost-optimal operating points for given demand and available supply resources (optimality problem). Currently, the available techniques to address these problems are prohibitively expensive, and system operators in practice are left with heuristic approaches with no accuracy guarantees. As an example, cascading failures in power grids can only be simulated up to the point where existing numerical techniques fail, which does not imply a blackout, but rather that the numerical method was started with bad parameters; regardless, it remains undecided whether the network can survive or not. This can cause the impacts of certain events to be overstated and others left unknown, resulting, more importantly, in misguided priorities to protect critical infrastructure against impactful events.

To prevent these shortcomings, our work developed a new global-solution approach for these problems that is also applicable to other feasibility and optimality problems with the same characteristics. The developed approach exploits elliptical structure in these problems to perform an efficient progressive adaptive partition of the search space, where each subdomain is either evaluated or discarded based on provable criteria, resulting in a proof that no solution exists or a global solution. The team developed extensions of the technique for conic structures and higher dimensions beyond the plane, greatly expanding the applicability of the approach to other problems. Test instances have shown that the proposed methodology can reduce the computational effort of solving these types of problems by a factor of four, compared with existing range (rectangular) partition approaches, and solve synthetic instances of power flow (feasibility) and optimal power flow (optimality). This provides positive evidence that our approach, in combination with existing techniques of different natures, can compute feasibility and optimality certificates in practical time frames for offline studies, where they are mostly required.

Mission Impact

This feasibility study marks the first step towards a practical global-solution approach for determining the operability and maximum efficiency of critical infrastructure, which results are key in achieving climate and energy resilience, as well as ensuring energy and resource security against adversaries. The resulting tools from this project will continue to be developed in support of multiple applications in E-program as we develop science and technology tools and capabilities around the core idea studied in the project to meet future national security challenges.