PaperlayerView exact revision on arXiv

Source-linked AI summary

Controlled Islanding and Reconnection with Stability Guarantees via Submodular Optimization

Shiyu Cheng, Andrew Clark

arXiv:2609.12335v1eess.SYcs.SY

TL;DR

Faults and disturbances can propagate through network interconnections and threaten overall stability, motivating controlled islanding and reconnection. The paper derives Lyapunov-based stability conditions and encodes the coupled decisions through a graphic matroid and supermodular formulation. Numerical studies illustrate the procedure, including a stable reconnected component in an example.

  • Problem

    Faults or disturbances may propagate through network interconnections and compromise overall stability, while islanding and reconnection decisions are coupled.

    Source: §I · p. 1

  • Method

    The paper derives Lyapunov-based sufficient conditions for both stages and represents admissible islanding and reconnection pairs through graphic-matroid bases and a supermodular formulation.

    Source: §I · p. 1, §V · p. 7, A. Matroid Reformulation and… · p. 9

  • Results

    In an illustrative example, the reconnected component has a minimum eigenvalue of 2.2520 > 0, verifying its asymptotic stability.

    Source: 1) Illustrative Islanding and… · p. 13

  • Takeaways & Limitations

    The framework treats the stability of post-islanding islands and reconnected components as requirements in the joint reconfiguration problem.

    Source: §I · p. 1, 1) Islanding · p. 4

Abstract

from arXiv · show

In large-scale networked dynamical systems, local faults or disturbances may propagate through the interconnections and compromise the stability of the entire network. Partitioning the network into disjoint subsystems, or islands, limits this propagation by isolating unstable portions of the network from those that remain stable. This paper studies a two-stage controlled islanding and reconnection problem. In the first stage, the network is partitioned into stable and unstable islands. In the second stage, selected stable islands are reconnected to recover connectivity lost during islanding while satisfying stability requirements. We derive Lyapunov-based sufficient conditions for both stages. To address the coupling between the islanding and reconnection decisions, we construct an augmented graph on which the bases of a graphic matroid induce exactly the admissible islanding and reconnection pairs. We further show that the resulting optimization problem admits an equivalent nonincreasing supermodular formulation. Based on this structure, we develop a local-search algorithm with counterexample refinement and establish a performance guarantee for its inner loop with fixed sample sets. Numerical studies on linear networked systems illustrate the proposed procedure, examine its sensitivity to fault locations, and compare the proposed method with a mixed-integer linear programming benchmark in terms of solution quality and computational performance.

I. INTRODUCTION

The paper addresses stability-aware network islanding and reconnection, where decisions in the two stages are coupled. It situates this problem among prior islanding and stability methods and introduces the graph, dynamics, and optimization concepts used in the paper.

I. INTRODUCTION

  • The framework combines Lyapunov-based stability conditions for islanding and reconnection with a graphic-matroid representation and nonincreasing supermodular objective.The resulting structure supports local search with a performance guarantee.Source: §I · p. 1

II. RELATED WORK

  • Prior islanding methods include spectral clustering, mixed-integer optimization –, and submodular optimization –; mixed-integer formulations can incorporate connectivity, coherency, power-flow, and load-generation constraints.The paper explicitly optimizes post-islanding reconnection decisions under dynamical stability requirements on the resulting reconnected components, unlike restoration work that incorporates blackstart availability into island formation.Source: §II · p. 2

A. Notation

  • The paper defines col for stacking vectors, writes x = col(x1, ..., xN) as a stacked vector, defines proj_I for indexed components, and defines Euclidean balls B(z, ϵ).For ordered I = {i1, ..., ik}, proj_I(x) = col(x_i1, ..., x_ik).Source: A. Notation · p. 2

B. System, Islanding, and Reconnection Models

  • The paper models a network as a connected undirected graph whose nodes have local dynamics and interact through edges.Islanding removes edges between connected islands; selected removed edges may later be restored.Source: B. System, Islanding, and Reconnection… · p. 2

C. Submodular Functions and Matroids

  • The preliminaries define submodularity and matroids, including bases, and recall that a graphic matroid’s bases correspond to spanning trees when its graph is connected.These concepts underpin the paper’s optimization reformulation.Source: C. Submodular Functions and Matroids · pp. 2–3

D. Labeled Multigraphs and Graphic Contraction

The paper formalizes islanding and reconnection as a stability-constrained, two-stage network reconfiguration problem. Its graph and multigraph preliminaries supply the structural language for describing these decisions.

D. Labeled Multigraphs and Graphic Contraction

  • A labeled multigraph treats edges as distinct elements even when they share endpoints, a distinction needed because contraction can create parallel edges while preserving edge identities.In a connected graph, the graphic matroid’s bases are its spanning trees.Source: D. Labeled Multigraphs and Graphic… · p. 3

1) Islanding:

  • A valid islanding partitions all nodes into nonempty, disjoint, connected islands, and the islanding stage seeks stable islands while limiting instability and edge-removal costs.The network is divided into stable and unstable islands after a disturbance.Source: §IV · p. 3

2) Reconnection:

  • After stable islands approach their equilibria, selected removed edges may be restored to reduce fragmentation, but each resulting reconnected component must remain stable.Only removed edges linking distinct stable islands are eligible for reconnection.Source: §IV · p. 3, 2) Reconnection · pp. 4–5

A. Problem Statement

  • The optimization minimizes the combined islanding and reconnection cost subject to stability of every stable island and every reconnected component.Reconnection can change the coupling among stable islands, so its stability requirement is separate from post-islanding stability.Source: 2) Reconnection · pp. 4–5

B. Optimization Formulation

The optimization formulation replaces trajectory-based stability requirements with Lyapunov sufficient conditions and penalties for their violations. Reconnection is certified by requiring the terms added by restored edges to be dominated by the islands’ decay margin.

B. Optimization Formulation

  • Lyapunov functions assembled from node-wise and pairwise terms provide sufficient stability conditions for post-islanding islands and reconnected components.For reconnection, added edge terms must be dominated by the decay margin available from the island conditions.Source: B. Optimization Formulation · pp. 5–6
  • The formulation penalizes violations of the sufficient stability conditions to make the trajectory-based requirements usable in the combinatorial optimization problem.The violation inequalities encode the pointwise conditions required by the stability propositions.Source: B. Optimization Formulation · p. 7
  • Zero violation of the islanding and reconnection inequalities enforces stability of every stable island and every reconnected component.The implication holds under the stated domain-regularity assumption that the relevant sublevel sets are closures of their interiors.Source: B. Optimization Formulation · p. 7
  • The optimization remains combinatorial because valid islandings grow combinatorially with network size and eligible reconnection edges depend on the islanding decision.These coupled decisions motivate the matroid-based solution method developed next.Source: B. Optimization Formulation · p. 7

V. MATROID AND SUBMODULAR REFORMULATION

The reformulation encodes coupled islanding and reconnection decisions in an augmented graph, then uses a supermodular objective to support local search with a performance guarantee.

V. MATROID AND SUBMODULAR REFORMULATION

  • An augmented graph represents each admissible islanding and reconnection pair through a single graphic-matroid basis selection.This replaces the coupled decisions with one optimization variable.Source: §V · pp. 7–8
  • The augmented-graph formulation addresses the combinatorial and coupling challenges in the original problem.The basis selection jointly captures the admissible islanding and reconnection decisions.Source: §V · pp. 7–8
  • The basis-constrained objective has an equivalent nonincreasing supermodular extension.The reformulation yields a local-search method with a provable performance guarantee.Source: §V · p. 8

A. Matroid Reformulation and Submodular Optimization

The section converts coupled islanding and reconnection choices into graphic-matroid basis selection, then reformulates the objective as nonincreasing and supermodular. Because exact evaluation involves continuous-state integration, the proposed procedure uses sampled local search with counterexample refinement.

A. Matroid Reformulation and Submodular Optimization

  • The augmented labeled multigraph uses auxiliary nodes and a contracted graphic matroid to represent the coupled decisions through spanning-tree bases.The construction preserves distinct edge elements, including parallel edges created by contraction.Source: A. Matroid Reformulation and… · p. 8
  • Each basis determines a unique admissible islanding–reconnection pair, and every admissible pair is induced by some basis.Different bases can encode the same pair, but the objective depends on the basis only through that pair.Source: A. Matroid Reformulation and… · p. 9
  • The original objective has an equivalent nonincreasing supermodular extension on the edge set.The component functions are nonincreasing and supermodular, and their weighted combination agrees with the original objective on matroid bases.Source: A. Matroid Reformulation and… · p. 10
  • Exact evaluation of two objective terms generally requires impractical continuous-state integration, motivating a sample-based approximation.For fixed sample sets, the sampled terms admit nonincreasing supermodular extensions.Source: A. Matroid Reformulation and… · pp. 10–11
  • The algorithm alternates feasible single-edge basis exchanges with counterexample refinement of the sample sets.It adds counterexamples associated with stability penalties and repeats local search until both counterexample sets are empty.Source: A. Matroid Reformulation and… · p. 11

B. Optimization Analysis

For fixed sample sets, the inner loop has a local-search performance guarantee and a bound on its search effort. The guarantee applies as the improvement tolerance approaches zero, while the evaluation count described here excludes outer-loop counterexample refinement.

B. Optimization Analysis

  • As bϵ → 0, the inner loop achieves at least half the maximum σ improvement over feasible bases, where σ(S)=eF(∅)−eF(S).The guarantee is for fixed sample sets and follows from local optimality under feasible single-edge exchanges.Source: B. Optimization Analysis · p. 11
  • Each inner-loop search evaluates at most O(M^2) candidate exchanges, with K accepted updates followed by one final search.This uses |E|=O(M), which follows from the construction and connectivity of the original graph.Source: B. Optimization Analysis · p. 12
  • The evaluation bound covers one inner-loop execution with fixed sample sets, not the outer counterexample-refinement iterations.Source: B. Optimization Analysis · p. 12

VI. NUMERICAL STUDIES

The numerical studies evaluate the framework on linear networked systems, from an illustrative islanding example to fault-location sensitivity and a MILP benchmark comparison.

VI. NUMERICAL STUDIES

  • The numerical evaluation uses linear networked systems and includes an islanding example, fault-location sensitivity study, and MILP benchmark comparison.Source: §VI · p. 12
  • The studies examine how results vary across fault configurations and compare solution quality and computational performance with a MILP benchmark.Source: §VI · p. 12
  • The implementation uses eigenvalue-based counterexample search for the linear systems considered.Source: §VI · p. 12

A. Linear Network Model and Counterexample Search

The numerical model represents a connected undirected network with node and edge coefficients; faults alter these coefficients and can destabilize the origin. Eigenvalue tests identify stability violations and generate counterexamples for the stability-penalty samples.

A. Linear Network Model and Counterexample Search

  • Faults change nominally positive node or edge coefficients to negative values, which may make Dw+L(E) lose positive definiteness and destabilize the origin.Source: A. Linear Network Model and… · p. 12
  • For an island, asymptotic stability is equivalent to λmin(Hr)>0; eigenvalues at or below 10^-9 trigger counterexample generation.The associated eigenvector direction is embedded in the full state, scaled to the boundary of Ω, and added to Ωsample.Source: A. Linear Network Model and… · p. 12
  • Counterexamples for reconnected components are constructed analogously, and eigenvalue tests verify actual asymptotic stability of islands and reconnected components.Source: A. Linear Network Model and… · p. 12
  • The Lyapunov-based penalties may remain positive even when all resulting components are asymptotically stable, so final stability is verified with eigenvalue tests.Source: A. Linear Network Model and… · p. 12

B. Numerical Results

The numerical results illustrate islanding and reconnection, test sensitivity to fault locations, and compare the proposed method with a MILP benchmark. The conclusion frames these studies within a coupled stability-aware optimization approach and identifies nonlinear collective behavior as future work.

1) Illustrative Islanding and Reconnection Example:

  • 2.2520 is the reconnected component’s minimum eigenvalue after one selected edge merges two stable islands, while the unstable island remains isolated.The original 30-node, 82-edge network is partitioned into two stable islands and one unstable island.Source: 1) Illustrative Islanding and… · p. 13, Figure 3 · p. 13

2) Sensitivity to Fault Configurations:

  • 742.9 s is the average computation time across ten fault configurations; F1 ranges from 19.0 to 35.6, and all runs converge before 20 outer iterations.The fault locations affect both computation time and islanding-and-reconnection cost.Source: 2) Sensitivity to Fault Configurations · p. 13

3) Comparison with the MILP Benchmark:

  • The MILP comparison uses four network sizes and reports inner solves, end-to-end time, and F1 under matched network, fault, and initial-sample settings.The two methods may generate different counterexamples, so the comparison reports F1 rather than final sampled objectives.Source: 3) Comparison with the MILP Benchmark · pp. 13–14, Table II · p. 13

VII. CONCLUSION

  • The conclusion identifies coupling between islanding and reconnection decisions as central: islanding determines available reconnections, which can affect component stability.The paper’s stated stability notion is convergence of an island or reconnected component’s states to the origin.Source: §VII · p. 14
  • The numerical studies cover linear systems; future work proposes extending the formulation to nonlinear systems with requirements such as synchronization.Source: §VII · p. 14

APPENDIX

The appendix provides technical details omitted from the main text.

APPENDIX

  • The appendix provides technical details omitted from the main text.Source: APPENDIX · p. 14

A. Proof of Lemma 9

The proof establishes that the constructed islanding is valid and that each component attaches to exactly one of the auxiliary vertices.

A. Proof of Lemma 9

  • The constructed islands partition the network and are connected, establishing a valid islanding.Paths within each component using edges in A also lie in the corresponding island graph.Source: A. Proof of Lemma 9 · p. 15
  • Each component has at least one edge in A connecting it to s0 or d0, with its endpoint in that component.This follows because A is a spanning tree and the component is formed after removing s0 and d0.Source: A. Proof of Lemma 9 · p. 15
  • Each component has exactly one such attachment edge; two would create a cycle in the spanning tree A.If the edges meet the same auxiliary vertex, the component path completes the cycle; if they meet different vertices, e0 completes it.Source: A. Proof of Lemma 9 · p. 15

B. Proof of Theorem 1

The proof establishes nonincreasing supermodularity by constructing basis-exact extensions for indicator-based terms and proving the property for F1, F2, and F3, thereby establishing it for F as their nonnegative weighted sum.

B. Proof of Theorem 1

  • Applying a fixed-set restriction and union transform to a monotone submodular function yields another monotone submodular function.This property is used in constructing the indicator extensions.Source: B. Proof of Theorem 1 · p. 15
  • The indicator extensions agree with their originals on bases and are nonincreasing and supermodular, including extensions for stable- and destination-side indicators and reconnection indicators.The proof also establishes these properties for the combined extensions of the indicator terms.Source: B. Proof of Theorem 1 · pp. 15–16
  • A signed-coefficient construction preserves nonincreasing supermodularity for either sign by using an extension of the indicator or of its complement.On matroid bases, the construction equals the original coefficient times the binary indicator.Source: B. Proof of Theorem 1 · p. 16
  • The recursive conjunction construction preserves basis agreement and nonincreasing supermodularity, enabling extensions of higher-order terms built through Γ.The proof applies this construction to conjunctions involving reconnection indicators, including cases where two indices belong to the same stable island.Source: B. Proof of Theorem 1 · pp. 16–18
  • F1’s extension agrees with the original objective on matroid bases and is nonincreasing and supermodular when its coefficients are nonnegative and 0 < α1 < α0.The proof establishes agreement by matching the extended indicators and their conjunctions to the original terms on bases.Source: B. Proof of Theorem 1 · p. 17
  • For each fixed x, Φv’s extension is nonincreasing and supermodular; nonnegative weights and integration over the fixed domain preserve these properties for F2.The weight functions are nonnegative, and the proof uses finite sums and integration over Ω.Source: B. Proof of Theorem 1 · p. 18
  • For fixed x ∈ bΩ, Ψv(x, ·) is nonincreasing and supermodular on 2^E, using the extension properties of T, the properties of Rr, and the definition of T.Lemma 15 supplies the required extensions for conjunctions in the first three groups; the fourth group uses properties of Rr, and the last two groups use the definition of T.Source: B. Proof of Theorem 1 · p. 19
  • F3 is nonincreasing and supermodular because finite sums preserve both properties and integration over the fixed domain preserves their inequalities.The preceding step establishes that the integrand is nonincreasing and supermodular in A.Source: B. Proof of Theorem 1 · p. 19
  • For α2, α3 ≥ 0, F is nonincreasing and supermodular on 2^E as a nonnegative weighted sum of F1, F2, and F3.On every A ∈ B(Mc), the proof also states F(A) = F1(A) + α2F2(A) + α3F3(A) = F(A).Source: B. Proof of Theorem 1 · p. 19
Loading 2609.12335v1…