Techniques for Efficient Interactive Configuration of Distribution Networks

Tarik Hadzic, Andrzej Wasowski, Henrik Reif AndersenIJCAI 2007

Abstract

This paper presents a framework for the interactive restoration of power distribution networks, enabling human operators to safely reconfigure grids after outages. By combining Binary Decision Diagrams (BDDs) with novel techniques such as early variable quantification, topology-aware variable ordering, and conjunctive decomposition, the authors scale interactive configuration to large-scale industrial power grids. The approach successfully manages NP-hard load constraints in real-time, providing a backtrack-free environment for operators.

Introduction

When a power grid fails, operators must reroute electricity to restore service. While automatic solvers exist, industrial partners often prefer interactive configuration. In this mode, a human makes choices, and the system provides real-time feedback by "pruning" invalid options—ensuring the operator never makes a choice that leads to a dead end or violates physical laws.

The challenge is that power networks are significantly harder to model than typical product configurators. They involve complex connectivity constraints to prevent short circuits and load constraints to ensure no power line exceeds its maximum capacity. While connectivity is computationally manageable, adding load constraints makes the problem NP-hard. Previous BDD-based approaches often suffered from state-space explosion, failing to compile models for even medium-sized networks.

Methodology

The authors introduce several techniques to make BDD compilation and real-time interaction feasible:

  • Early Variable Quantification: Since operators primarily care about whether a sink or line is active, the system "hides" (quantifies out) complex internal load variables as early as possible during BDD construction.
  • Topology-Aware Ordering: BDD performance depends heavily on variable ordering. The authors use the physical layout of the grid, applying Minimum Linear Arrangement (MINLA) to place geographically close variables near each other in the BDD structure.
  • Conjunctive Decomposition: For the largest instances, the grid is broken into overlapping geographical regions, each with its own BDD. A synchronization algorithm (RESTORE-CONSISTENCY) passes messages between these BDDs to ensure global consistency across the entire network in real-time.
Figure 2: Visualization of a complex power grid instance partitioned into regions $R_1$ through $R_4$ for conjunctive decomposition.

Experimental Results

The study utilized real-world industrial power grid instances provided by NESA A/S. The "Complex" instance, featuring 146 lines and 119 sinks, was successfully handled using conjunctive decomposition—a task previously considered computationally unreachable.

Figure 4: Comparison of BDD sizes and instance complexity, demonstrating the effectiveness of early quantification.

As shown in the table above, early quantification drastically reduces BDD size. For the Std-diagram, the size was reduced from 215kb to just 7.3kb. On a 3.2GHz PC, calculating valid domains for the "Complex" instance took less than 0.5 seconds, and restoring global consistency across decomposed regions took less than 3 seconds. These results demonstrate that the proposed abstraction and decomposition methods enable real-time performance on large-scale industrial datasets.

Conclusion

The complexity gap between connectivity and load constraints necessitates specialized BDD techniques for power grid configuration. By abstracting internal variables and adopting a "divide and conquer" approach through conjunctive decomposition, this framework successfully bridges the gap between theoretical NP-hardness and practical industrial application. Future work will focus on automating decomposition heuristics and exploring alternative symbolic representations.

Summary updated

BibTeX
@inproceedings{hadzic2007techniques,
  author = {Tarik Hadzic and Andrzej Wasowski and Henrik Reif Andersen},
  title = {{Techniques for Efficient Interactive Configuration of Distribution Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure