Search Strategies for Topological Network Optimization

Michael D. MoffittAAAI 2022 · DOI

Abstract

Topological network design involves constructing a network from a set of components to achieve a specific target value, a task significantly more complex than standard network analysis. This paper introduces a high-performance combinatorial search algorithm for series-parallel networks. By integrating recursive decomposition trees with novel pruning and convexity-based tabulation, the algorithm achieves over a 45x speedup compared to baseline methods, allowing for the optimal design of networks with up to 12 components.

Introduction

In traditional network theory, researchers typically analyze "static specifications"—calculating properties like shortest paths or maximum flow through a fixed topology. Topological network design reverses this paradigm: the objective is to determine the optimal arrangement of a given set of components (e.g., resistors) to meet a specific target value.

This problem is notoriously NP-hard. The solution space is vast because the "shape" of the network—how components are nested in series and parallel configurations—is as critical as the component values themselves. While previous methods relied on brute-force enumeration or heuristic local searches, this work provides a fast, exact method for series-parallel optimization.

Methodology: Decomposition Trees and Search Strategies

The core of the proposed approach is the use of Decomposition Trees. These trees represent series and parallel connections as alternating layers, providing a structured way to explore the combinatorial space.

A decomposition tree representing series and parallel connections between components.

The search algorithm employs three primary strategies:

  1. Recursive Decomposition: The algorithm explores the space by taking a component set and testing all possible $k$-way partitionings to build the tree top-down.
  2. Monotonic Pruning: Since series ($f_+$) and parallel ($f_{||}$) operators are monotonic, the algorithm calculates bounds for partial networks. Branches that cannot possibly surpass the current best solution are pruned.
  3. Convexity-based Tabulation: Recognizing that the objective function is convex relative to subcircuit values, the author uses binary search over precomputed tables for "singleton expandables" and a "dual linear sweep" for pairs of subcircuits. This reduces quadratic search spaces to linear ones.

Key Insights: Why Structure Matters

Unlike simple number partitioning, network optimization is highly sensitive to topology. Shuffling components between subsets can lead to vastly different outcomes because of how the series and parallel operators interact.

Two different topologies using the same set of components, illustrating how structural changes affect the final network value.

Furthermore, the "0-Ω Trick"—adding a zero-ohm resistor (a wire) to the component set—allows the algorithm to effectively "remove" unnecessary components, facilitating the discovery of the optimal subset for any given target.

Experimental Results

The algorithm was evaluated using a benchmark suite of electrical circuits with resistors from the standard E12 series, aiming to approximate $\sqrt{n}$ for $n$ components.

  • Performance: The combined pruning and tabulation approach is up to 45x faster than exhaustive baselines.
  • Scalability: The solver successfully handled problems up to $n=12$. For $n=9$, it achieved zero error; for $n=12$, it found approximations accurate to eleven decimal places.
  • Quality: Compared to stochastic local search, the exact solver produced solutions with costs four times lower within the same time constraints.

Conclusion and Future Work

While the algorithm significantly pushes the boundaries of exact topological search, the problem remains fundamentally exponential. Future research may extend convexity-based optimizations to handle more than two "expandable" nodes or adapt the framework for non-series-parallel "bridge" circuits.

Summary updated

BibTeX
@inproceedings{moffitt2022search,
  author = {Michael D. Moffitt},
  title = {{Search Strategies for Topological Network Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21271},
}

Loading related content...

Figure