Submodular optimization in risk mitigation : modeling, approximation algorithm, and theoretical analysis

Abstract

Current power system suffers greatly from blackout risk caused by increasing power demand and large renewable integration. However, traditional risk mitigation approaches require large investment and are susceptible to natural features and machine properties. With the help of sensor technique development, power system planners can place devices such as dynamic thermal rating (DTR) sensor with less burden, to fully utilize the existing transmission capability based on environment data, thus illustrating great potential for mitigating system risk. However, sensor placement for risk mitigation is a combinatorial optimization problem, which is NP-hard to solve.

Submodularity refers to the diminishing return property in discrete functions. For a combinatorial optimization problem that possesses submodularity, submodular optimization scheme offers a rigorous mathematical framework and analytical approach for resolution. Although submodular optimization has found application in various domains such as system planning and machine learning, its application in power system risk mitigation has remained unexploited prior to this work. Thus, this thesis focuses on the risk mitigation within the framework of submodular optimization, including submodular modeling, approximation algorithm design, and corresponding theoretical analysis. Specifically, the detailed research are as follows.

First, a submodular optimization model of DTR placement is proposed for risk mitigation considering Braess paradox. In detail, a model based upon important sampling weight is utilized to efficiently quantify the failure risk and analytically reveal the Braess paradox condition. And a novel submodular optimization approach is established to maintain the function submodularity in risk mitigation model. To address this non-monotone submodular optimization efficiently, a tailored algorithm is designed based on a modified double greedy algorithm, and a comprehensive theoretical analysis is carried out to support the approach.

Second, a robust submodular DTR placement model is established considering both risk mitigation and maximal wind integration. In particular, a fast estimation scheme based on general important sampling weight is devised to efficiently estimate the interaction among DTR placement, risk mitigation and maximal wind integration. Subsequently, a generalized form of robust submodular optimization is formulated to model this multi-objective combinatorial problem, allowing for dimensional inconsistency and flexible decision preferences across different sub-objectives. A corresponding solving algorithm is designed based upon saturated greedy approach, and relevant theoretical analysis is conducted.

Third, a two-stage submodular optimization (TSSO) model is constructed for DTR’s placement and operation schedule. Under the condition of the Markov and submodular features in sub-function of risk mitigation, the submodularity of total objective function of TSSO can be proven. Based on this, a state-of-the-art efficient solving algorithm is developed by coordinating the separate curvature and error form, accompanied by related theoretical analysis.

Finally, to quantitively assess scenario selection process in risk mitigation, an assessment scheme for generalized forward scenario selection is developed. Specifically, an index termed process submodular ratio is established to provide a total guarantee consisting of pure guarantee and gap form, which can quantitatively evaluate and visualize the performance during the selection process. And a tail cost index is formulated via power-law exponent, which can dynamically estimate the selection cost.