PaperlayerView exact revision on arXiv

Source-linked AI summary

The N-K Problem in Power Grids: New Models, Formulations and Numerical Experiments (extended version)

Daniel Bienstock, Abhinav Verma

arXiv:0912.5233v2math.OC

TL;DR

The paper studies whether removing a small number of transmission lines can make a power grid fail, a difficult problem because attacks interact with network topology and physical power-flow constraints. It develops mixed-integer and continuous nonlinear optimization models for this attacker-controller problem. The formulations substantially reduce pure enumeration, with the continuous nonlinear approach reported as particularly scalable, while the analysis remains limited by its approximate DC power-flow model.

  • Problem

    The N-k problem asks whether a small set of removed power lines can cause grid failure, requiring vulnerability analysis that accounts for combinatorial attacks and power-flow physics.

  • Method

    The paper formulates an attacker-controller model using a linear mixed-integer program and a continuous nonlinear program.

  • Results

    The formulations provide substantial savings over pure enumeration, and the continuous nonlinear formulation handles models an order of magnitude larger than previously reported examples.

  • Takeaways & Limitations

    Modeling generator decisions, load shedding, and physical network constraints enables computational analysis of small, hidden grid vulnerabilities.

  • Takeaways & Limitations

    The approach uses an approximate DC power-flow model rather than the more accurate nonlinear AC formulation, trading physical fidelity for tractability.

Abstract

from arXiv · show

Given a power grid modeled by a network together with equations describing the power flows, power generation and consumption, and the laws of physics, the so-called N-k problem asks whether there exists a set of k or fewer arcs whose removal will cause the system to fail. The case where k is small is of practical interest. We present theoretical and computational results involving a mixed-integer model and a continuous nonlinear model related to this question.

1 Introduction

The paper frames the N-k problem as finding small, hidden vulnerabilities in otherwise robust power grids while accurately modeling power-flow physics. It focuses on the difficult middle range of attack sizes and introduces mixed-integer and continuous nonlinear optimization models.

  • Recent blackouts show how small initial line failures can develop into severe system collapse.
  • The vulnerability evaluation problem asks whether removing a small set of power lines can cause system failure, with practical interest in k = 3 or 4.
  • The N-k problem is difficult because attack enumeration grows combinatorially and power flows require accurate yet tractable physical models.
  • The primary focus is 2 ≤ k ≤ 5, which is both operationally relevant and harder than the easily enumerable k = 1 case.
  • The paper presents a mixed-integer attacker-controller model and a continuous nonlinear formulation that substantially reduce reliance on pure enumeration.
  • The analysis uses linearized DC power flows, which approximate AC physics but make the underlying combinatorial problem more computationally tractable.

2 The “N - k” problem

The N-k formulation models an attacker removing arcs against a controller that can choose generators, outputs, and load shedding to preserve throughput. The paper develops structural defeat conditions and highlights non-monotonic attack behavior caused by generator choices and power-flow constraints.

  • The attacker removes arcs while the controller selects operating generators, generation levels, and demands to maintain feasible high-throughput operation.
  • An attack is successful only if it defeats every generator configuration by either reducing maximum throughput below T_min or making feasibility impossible.
  • The min-cardinality problem seeks a successful attack with the fewest removed arcs, whereas the budget-k min-throughput problem fixes the attack budget and minimizes throughput.
  • Attacks can defeat configurations through demand-supply mismatches across partitions, generator lower bounds, or infeasible power-flow and capacity constraints.
  • The formulation supports general nonnegative generator minimum outputs and can be solved directly by commercial integer-programming software when all lower bounds are zero.
  • The examples exhibit non-monotonicity: a successful attack can exist with k = 1 while no successful attack exists with k = 2.
  • The paper connects such non-monotonicity to Braess’s Paradox and to controller choices among generators with positive minimum outputs.

2.1 A mixed-integer programming algorithm for the min-cardinality problem

The algorithm alternates between an attacker master problem and a controller search for generator configurations that survive a proposed attack. Valid inequalities and Benders-style cuts iteratively tighten the relaxation, while numerical tolerances and disconnected networks create implementation constraints.

  • Basic algorithm for min-cardinality attack problem: The min-cardinality algorithm iteratively solves a master attacker MIP and searches for a generator configuration that can withstand the proposed attack.If no such configuration exists, the attack is certified successful; otherwise, valid inequalities are added and the process repeats.
  • Controller problem: An attack defeats a configuration exactly when the controller’s minimum maximum arc overload exceeds 1.The controller’s linear program seeks to satisfy demand without exceeding arc capacities, with t representing the minimum maximum overload.
  • Basic algorithm for min-cardinality attack problem: The master formulation is initially impractical because it contains an exponential number of constraints without a compact representation.The algorithm addresses this by adding valid inequalities that cut off unsuccessful master solutions.
  • Basic algorithm for min-cardinality attack problem: The master objective remains a lower bound on the cardinality of any successful attack, so the exit condition certifies optimality.When no surviving controller configuration is found, the attack implied by the master solution is successful and minimum-cardinality.
  • Benders-style implementation: Benders cuts require a combinatorial dual because attack variables affect both the first-stage master and the controller’s second-stage problem.The procedure dualizes the problem without an attack, adds attack variables and linking constraints, then fixes them to the incumbent attack.
  • Benders-style implementation: A small tolerance gives the controller more power, excluding borderline attacks from being classified as successful and preventing exact optimization of the strict model.The authors expect negligible practical impact when the tolerance is small, but borderline attacks require interpretation.
  • Numerical considerations: The big-M constants should remain small because power-flow linear programs can exhibit numerical instability and network-scaled constants would make the approach nonscalable.Small constants also tighten the linear-programming relaxation, but numerical behavior is identified as the primary practical reason.
  • Numerical considerations: The initial formulation is inadequate when an attack disconnects the network because reasonable upper bounds on certain dual variables then appear unavailable.The paper therefore introduces a different formulation while retaining the broader algorithmic methodology.

2.2 A better mixed-integer programming formulation

The improved mixed-integer formulation models attacker–controller interaction through generator configurations, dualization, Benders cuts, and strengthened inequalities. It provides optimality certificates, network-size-independent bounds for M, and cuts linking flow conservation with Ohm’s law.

  • 2.2 A better mixed-integer programming formulation: The improved formulation uses binary generator indicators and dual constraints to represent the controller’s response for a fixed generator configuration.The formulation is rewritten in matrix form before generator indicators are allowed to become 0/1 variables.
  • 2.2 A better mixed-integer programming formulation: The improved controller has substantially more power because it need not force attacked-arc flows to zero, but constraint (37) still detects attacks carrying flow.Specifically, t∗C(zA) > 1 whenever any attacked arc carries flow.
  • 2.2 A better mixed-integer programming formulation: The controller’s problem determines whether some generator configuration defeats a proposed attack, with t∗(zA) ≤1 certifying such a configuration exists.This condition underlies the improved attacker–controller formulation.
  • 2.2 A better mixed-integer programming formulation: The formulation is exponentially large, so the algorithm instead adds Benders cuts generated from optimal dual solutions and iteratively updates the attacker master problem.Full controller systems may also be added selectively, while cuts from different configurations reinforce one another.
  • 2.2 A better mixed-integer programming formulation: If every generator configuration satisfies t∗C(zA) > 1, the algorithm certifies that the proposed attack solves the min-cardinality problem to optimality.The attack is successful when no controller configuration can maintain the required performance.
  • 2.2.1 Setting M: A valid choice of M is derived without allowing it to grow with network size by analyzing connected components after an attack.The proof uses incidence-matrix structure and bounds on the associated dual variables.
  • 2.2.2 Tightening the formulation: The tightening inequalities capture the interaction between flow conservation and Ohm’s law and strengthen the attacker system.When used in the algorithm, they enter either the master problem or the expanded dual vector with two new dual variables per arc.
  • 2.2.3 Strengthening the Benders cuts: Standard Benders cuts can be weak because early master iterations produce attacks with very small cardinality, motivating routines that generate stronger cuts.The strengthened cuts generally improve on cuts from stronger configurations, although power-flow non-monotonicity limits that guarantee.

2.3 Implementation details

The implementation uses the updated algorithm with strengthened Benders cuts and retains up to two full controller systems in the relaxation at a time.

  • 2.3 Implementation details: The implementation strengthens Benders cuts and maintains up to two full systems (56)-(58) in the relaxation.A full system added at iteration k is replaced at iteration k + 4 by the system associated with a later generator configuration.

2.4 Computational experiments with the min-cardinality model

Experiments evaluate the min-cardinality model across standard and artificial networks, testing scalability with network size, generator configurations, attack cardinality, and throughput thresholds. The results indicate that topology is the primary complexity driver, while generator count has a weaker effect and cutting planes limit enumeration.

  • Experimental goals: The algorithm’s performance study examined growth with network size, generator count, and instance features that could cause rapid iteration or runtime increases.The motivation was to assess whether generator configurations create prohibitive combinatorial complexity beyond prior instances with at most 79 arcs.
  • Results: With 8 rather than 4 generators on the 49-node network, an attack of cardinality 5 was needed to reduce throughput below 84%, versus cardinality 3 with 4 generators.The 8-generator case was more resilient even though total generator capacity was unchanged.
  • Results: Runtime did not significantly degrade when generator configurations increased sixteenfold on the 49-node network, and generator count likewise lacked an exponential runtime impact on the 98-node network.The 98-node, 204-arc case involved over 30,000 generator configurations that had to be examined at least implicitly for some certifications.
  • Interpretation: Overall, generator count played a second-order role, while topological network structure was the primary driver of algorithmic complexity.The total number of iterations depended only weakly on the number of generator configurations.
  • Interpretation: Cutting planes appeared to limit enumeration by exploiting structure to establish lower bounds on the minimum attack cardinality needed for success.When no attack succeeds, pure enumeration would need to test all attacks; when successful attacks exist, lower throughput thresholds make finding one harder.
  • One-configuration problems: The formulation was also reported as significantly effective on one-configuration problems, while larger attack cardinalities generally became easier because more optimal-attack candidates existed.The one-configuration tests most closely matched prior literature studies.

3 A continuous, nonlinear attack problem

The section introduces a continuous nonlinear attack model that perturbs line resistances to represent degraded or disabled transmission arcs and captures their interaction with power-flow physics. Its attack budget approximates concentrating large resistance increases on a small number of arcs while permitting smaller perturbations elsewhere.

  • Motivation: The formulation targets the interaction between flow conservation, power-flow equations, and network structure that drives the complexity of combinatorial power-flow attacks.It also reflects the possibility that real outages involve stressed systems and impaired lines rather than only discrete failures.
  • Attack model: Increasing an arc’s resistance can model diverse line impairments and, when sufficiently large, generally forces its power flow to zero.This provides a continuous representation of effects that might otherwise be modeled as outright line removal.
  • Attack model: The model lets an attacker choose arc resistances within a prescribed feasible set while generator outputs and demands remain fixed.The attacker maximizes overload on an arc, with resulting flows determined by the power-flow model.
  • Attack model: The conductance formulation permits an attack budget that roughly makes up to k arcs highly resistive without decreasing other resistances.The budget construction is designed to resemble the classical N-k problem while allowing continuous perturbations.
  • Model behavior: The continuous model differs from the standard N-k problem, but computational experience finds solutions at or near extreme points and indicates a more effective approach.The passage reports this behavior as computational experience rather than a general theoretical guarantee.

3.1 Solution methodology

The solution methodology reformulates the nonlinear attack problem for numerical optimization using compact power-flow representations and efficient derivative calculations. The approach accepts local-optimum limitations while targeting scalable computation for networks with roughly 1000 arcs.

  • Optimization framework: The nonlinear problem is smooth after reformulation but nonconcave, so nonlinear optimization methods provide no guarantee of finding a global optimum.A branch-and-bound procedure could in principle seek the global optimum, but the authors defer that work.
  • Optimization framework: The authors choose nonlinear optimization to preserve richer problem representations and an agnostic treatment of hidden network weaknesses.They contrast this with heuristics or methods that impose structural assumptions about the optimum.
  • Computational scope: The approach is reported to handle problems with on the order of 1000 arcs while retaining the model’s nonlinearities and agnostic search.The paper emphasizes both representational richness and computational scalability.
  • Derivative computation: Efficient numerical iterations require routines for the objective, gradient, and Hessian, whose cumulative computation can dominate runtime in large-scale settings.The paper develops representations intended to make these evaluations efficient.
  • Compact formulation: The method constructs a compact representation using essentially conductance variables rather than separate flow and phase-angle variables.The resulting evaluations use sparse linear algebra and support fast convergence in large instances.
  • Power-flow representation: Given conductances, the fixed net-supply vector determines power flows and voltages through a linear system under the model’s stated assumptions.The analysis assumes conditions ensuring convergence of the associated series representation.

3.2 Relationship to the standard N-k problem

The continuous model is theoretically connected to standard N-k attacks by making selected arc resistances very large. Experiments indicate that optimized attacks concentrate most of their budget on a small set of arcs while distributing smaller amounts across more lines.

  • Relationship to N-k: Under the lemma’s conditions, assigning very small conductances to a set of arcs relates the resulting power flow to the flow on the network with those arcs removed.The set must satisfy the stated condition that its removal does not disconnect the network.
  • Relationship to N-k: The continuous attack pattern corresponds to making selected resistances very large while leaving other arc resistances unchanged.This gives a continuous analogue of discrete line removal.
  • Computational interpretation: Computational experiments show that attacks tend to concentrate most of their budget on a small number of arcs while allocating a smaller portion to more lines.The observed pattern is described as approximately matching the lemma’s attack structure.

3.3 Efficient computation of the gradient and Hessian

The paper derives closed-form gradient and Hessian expressions for the nonlinear objective using recursive matrix representations of power-flow sensitivities. These formulas are intended to make derivative evaluation efficient for numerical optimization.

  • Derivative formulas: The section develops efficient closed-form expressions for the gradient and Hessian of the attack objective.The formulas are built from the network incidence vectors associated with arcs.
  • Implementation: The recursive representation is used to write the derivative expressions in a form suitable for efficient evaluation.The stated goal is computational rather than merely formal characterization.
  • Gradient: The gradient of each flow function with respect to conductance variables is expressed using the matrix-series representation introduced earlier.The derivation uses arc incidence columns and the associated recursive formulas.
  • Hessian: Second-order derivatives are developed similarly for pairs of arc variables, with terms combining the corresponding incidence vectors and matrix-series factors.The section supplies separate expressions for distinct arc pairs and remaining terms.

3.4 Implementation details

The implementation combines LOQO’s primal-dual interior-point procedure with custom derivative and linear-system computations, using compact problem representations and explicit stopping rules.

  • Solver and stopping criteria: LOQO applies an infeasible primal-dual interior-point method to successive quadratic approximations, with an iteration limit and additional stopping criteria.The procedure stops when primal and dual feasibility coincide with sufficiently close objective values, indicating a local optimum.
  • Derivative and linear-system computations: Each LOQO iteration computes objective Hessians and gradients by evaluating cᵀ_uvJ^-1c_ij for arc pairs and storing these quantities in O(n^2 + nm) space.For each pair, the implementation solves a sparse linear system in κ and λ, using CPLEX or another efficient linear algebra package.
  • Compact formulation: The preferred approach uses fewer variables than symbolic differentiation formulations by omitting flow variables and angles, thereby simplifying primal feasibility.The authors identify this reduced representation as the paper’s “compactness” ingredient.
  • Solver and stopping criteria: The implementation reports an ε-locally-optimal solution when the relative primal-dual error falls below a prescribed threshold.If the iteration limit is reached, it uses the last iteration with both primal and dual feasible solutions, when one exists.

3.5 Experiments

The experiments examine scalability, solver stability, solution structure, starting-point sensitivity, and agreement with the standard N-k model. The nonlinear algorithm scales to networks near 1,000 arcs, remains stable as ΔB changes, and produces concentrated attacks with substantial overlap across models.

  • Experiment goals: The experiments test scaling with network size and ΔB, solver stability, starting-point sensitivity, solution structure, and comparison with the standard N-k model.The study includes networks ranging from small test cases to approximately 1,000 arcs.
  • Scalability: The algorithm appears to scale reliably to approximately 1,000 arcs, after which LOQO begins to develop difficulties.The reported experiments evaluate networks including 600 nodes and 990 arcs and 649 nodes and 1,368 arcs.
  • Scalability: The workload remains stable as ΔB increases, without combinatorial growth in running time or iterations.Although larger ΔB permits more arcs to be maximally interdicted, the computational burden does not increase combinatorially.
  • Alternative starting points: Starting-point changes produce at most a 1.5% difference in congestion while leaving the set of heavily interdicted arcs unchanged.The authors describe this pattern as typical across their experiments.
  • Solution structure: The nonlinear solutions concentrate high resistance on a few arcs while assigning smaller attack portions to many others.For Γ(2), the experiments report three top-range arcs in the 300-node network and two top-range arcs plus one relatively high-resistance arc in the 600-node network.
  • Comparison with the minimum-cardinality attack model: The nonlinear and standard N-k models show substantial overlap, including high correlation among attacked lines for σ = 1.2, 1.4, and 1.6.Both models also show decreasing maximum congestion as the capacity-scaling parameter increases.
  • Comparison with the minimum-cardinality attack model: The nonlinear attack remains robust when the controller reduces total demand, with congestion decreasing proportionally.The results also indicate that low-x_ij arcs contribute materially to the attack’s impact.

3.6 Future work

The nonlinear-model experiments were highly encouraging, while follow-up work targets global optimization and more complex power-flow models.

  • The authors report highly encouraging experiments with the nonlinear model.
  • A follow-up project aims to embed the approach in a global optimization procedure.
  • Another ongoing project extends the ideas to more complex power-flow models.
Loading 0912.5233v2…