Mixed Integer Nonlinear Programming Approaches to Enhance Resiliency and Response Strategies in Critical Infrastructure

Abstract

Motivation. Critical infrastructures are large, complex engineered systems that must be operated robustly under abnormal conditions resulting from natural hazards or intentional acts. For example, electric power systems must be robust to line faults, water utilities must rapidly mitigate contamination incidents, and computing networks must adapt to adversarial intrusions to protect critical information. Problem. It is difficult for decision-makers within resiliency analysis in critical infrastructure to optimize designs and develop effective response strategies that can account for uncertainties. Facing incomplete information and the sheer scope that a natural hazard or attack vector may incorporate, response can be ineffective without reliable, scalable decision support tools. These problems are intrinsically nonlinear and involve discrete decisions, and unfortunately, existing off-the-shelf mathematical programming methods cannot support optimization-based decision-making of these nonlinear at scale. Method/Approach and Results. This project emphasized development of fundamental optimization strategies that supported real- time mitigation and response for critical infrastructures. In particular, the project developed multi- tree approaches based on piecewise outer-approximations for solution of mixed-integer nonlinear programming (MINLP) problems. These techniques alternate between an MILP or MISOCP relaxation to obtain a lower bound and candidate discrete solutions and an NLP subproblem to obtain upper bounds. Using tailored relaxations based on problem structure, these methods were used to solve several key applications in resilience and response of critical infrastructure. This work resulted in two open-source, copyrighted software packages: CORAMIN (https://github.com/Coramin/Coramin) -- an object-oriented mathematical programming framework that supports tailored multi-tree algorithms for solution of large- scale mixed-integer nonlinear programming; and EGRET (Electrical Grid Research and Engineering Toolkit) (https://github.com/grid- parity-exchange/Egret) -- a declarative mathematical programming framework built upon CORAMIN and Pyomo for formulation and solution of resilience and operations problems in power grid systems. Furthermore, these tools resulted in several important published results, including the following: The first known global optimization approach that could solve the unit-commitment problem with nonlinear power flow constraints on medium-sized test problems; Improved parallel optimization-based bounds tightening and strengthening of relaxations of AC power flow constraints; and, Optimization-based approaches for improved grid resilience and use of demand response to improve grid resilience with reduction in capital requirements. Result Implications. This project developed first-of-a-kind algorithms for decision-making in critical infrastructure resilience operations and planning, as well as a next-generation toolkit for MINLP researchers. These approaches leveraged high-performance computing architectures to solve some of the largest, most challenging nonlinear discrete optimization problems to global optimality, and these successes were captured in open-source software to enable optimization-based decision-making, and efficient solution of MINLP formulations for electric power transmission grids.