2025-11-24T14:52:17.958368

FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks

Gallart, Bent, Kia

This paper considers an optimal radial reconfiguration problem in multi-source distribution networks, where the goal is to find a radial configuration that minimizes quadratic distribution costs while ensuring all sink demands are met. This problem arises in critical infrastructure systems such as power distribution, water networks, and gas distribution, where radial configurations are essential for operational safety and efficiency. Optimal solution for this problem is known to be NP-hard. In this paper, we prove further that constructing a feasible radial distribution configuration is weakly NP-complete, making exact solution methods computationally intractable for large-scale networks. We propose FORWARD (Feasibility Oriented Random-Walk Inspired Algorithm for Radial Reconfiguration in Distribution Networks), a polynomial-time algorithm that leverages graph-theoretic decomposition and random walk principles to construct feasible radial configurations. Our approach introduces novel techniques including strategic graph partitioning at articulation points, dual graph condensation to address greedy shortsightedness, and capacity-aware edge swapping for infeasibility resolution. We provide rigorous theoretical analysis proving feasibility guarantees and establish a compositional framework enabling parallel processing while preserving optimality properties. Comprehensive numerical evaluation on networks ranging from IEEE standard test systems to 400-node small-world networks demonstrates that FORWARD consistently outperforms commercial MINLP solvers, achieving optimal or near-optimal solutions in seconds where traditional methods require hours or fail entirely. The algorithm's polynomial-time complexity and scalability make it particularly suitable for real-time distribution network management and as an effective initialization strategy for iterative optimization solvers.

academic

FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks

基本信息

论文ID: 2510.08785
标题: FORWARD: A Feasible Radial Reconfiguration Algorithm for Multi-Source Distribution Networks
作者: Joan Vendrell Gallart (UC Irvine), Russell Bent (Los Alamos National Laboratory), Solmaz Kia (UC Irvine)
分类: math.OC (Optimization and Control)
发表时间/会议: 2025年10月9日提交至arXiv，初步版本发表于2025 American Control Conference
论文链接: https://arxiv.org/abs/2510.08785v1

摘要

本文研究多源分布式网络中的最优径向重构问题，目标是找到一个径向配置，在满足所有汇点需求的同时最小化二次分布成本。该问题出现在电力分布、水网络和天然气分布等关键基础设施系统中，其中径向配置对运营安全和效率至关重要。作者证明了构建可行径向分布配置是弱NP完全问题，提出了FORWARD算法——一个多项式时间算法，利用图论分解和随机游走原理构建可行的径向配置。该方法在IEEE标准测试系统到400节点小世界网络上的综合数值评估表明，FORWARD始终优于商业MINLP求解器，在传统方法需要数小时或完全失败的情况下，能在几秒钟内获得最优或近最优解。

研究背景与动机

问题定义

本文要解决的核心问题是多源分布式网络中的最优径向重构问题。具体而言，给定一个包含多个源节点和汇节点的分布网络，需要找到一个径向配置（无环的树状结构），使得：

满足所有汇点的需求
最小化网络中的二次分布成本
遵守容量约束

问题重要性

该问题在多个关键基础设施领域具有重要意义：

电力系统：径向配置确保系统稳定性和安全运行，同时最小化功率损耗
水网络：确保供水安全和效率
天然气分布：保证安全运输和成本控制

现有方法局限性

传统方法主要存在以下问题：

计算复杂度高：MINLP方法在大规模网络上计算时间呈指数增长
可扩展性差：商业求解器在处理400+节点网络时经常失败
实时性不足：无法满足实时网络管理的需求
初始化困难：启发式方法难以找到可行域内的初始点

研究动机

作者的研究动机源于：

证明可行解构建问题的计算复杂度（弱NP完全）
开发能够在多项式时间内找到可行解的算法
提供适用于实时网络管理的高效解决方案

核心贡献

理论贡献：首次证明了多源分布网络中构建可行径向配置是弱NP完全问题，为该问题的计算难度提供了理论基础
算法创新：提出FORWARD算法，具有O(n²log n)的多项式时间复杂度，包含五个核心组件：
- Pre-Processor：简化网络结构
- Islander：图分解和并行处理
- Net-Concad：双图凝聚技术
- Sampler：基于权重的边采样
- Rewire：容量感知的边交换
理论框架：建立了组合可行性定理（Theorem 5）和最优性保持推论（Corollary 6），证明了图分解方法的理论正确性
性能突破：在大规模网络测试中显著优于商业MINLP求解器，在传统方法失败或需要数小时的情况下，能在几秒内获得解

方法详解

任务定义

给定分布网络GD = G(VD, ED)，其中：

输入：N个节点，m条边，ng个源节点集合Vg，nc个汇节点集合Vc
约束：输入向量g，输出向量d，容量约束x̄，满足∑gi = ∑di
输出：径向配置S和流量分布x，最小化目标函数：

$\min \sum_{(i,j) \in S} C_{i,j} \cdot x_{i,j}^2$

受约束：

G(VD,S) ∈ F (径向配置约束)
0 ≤ x(S) ≤ x̄(S) (容量约束)
A(S)x(S) = g - d (流守恒约束)

模型架构

1. Pre-Processor组件

功能：识别和处理网络中的悬挂节点
算法：迭代处理度数为1的节点，将其需求/供应传递给父节点
复杂度：O(n + m)
输出：2-core子图GP和已采样边集S

2. Islander组件

功能：在关节点处分解2-core子图
策略：仅在源关节点处分割，减少计算复杂度
平衡：调整分离节点的节点值以确保各子图输入输出平衡
输出：L个平衡的子图{G1, G2, ..., GL}

3. Net-Concad组件

功能：双图凝聚，解决贪心算法的短视问题
方法：
- 将已采样的多树合并为超级"已采样"节点
- 将未采样的连通分量合并为超级"未采样"节点
- 构建准二分图结构Ḡℓ

4. Sampler组件

功能：基于权重选择最优边进行采样
权重函数：wi,j = pi/(Ri,j · d²j + f̂(Ri_k))
优先级：
1. 悬挂超级未采样节点
2. 具有足够容量的边
3. 权重降序排列

5. Rewire组件

功能：通过边交换解决容量约束导致的不可行性
策略：
- 识别未供应节点和过剩供应路径
- 执行战略性边交换
- 维护径向结构

技术创新点

1. 图分解理论

创新：证明了组合可行性定理，建立了原问题与分解子问题之间的等价关系优势：支持并行处理，同时保持最优性

2. 双图凝聚技术

创新：Net-Concad函数通过构建准二分图结构克服贪心选择的短视性机制：将复杂的多源多汇问题转化为更简单的超级节点之间的连接问题

3. 容量感知边交换

创新：Rewire函数通过战略性边交换解决容量瓶颈原理：从过剩供应区域重新分配流量到未供应节点，而不需要额外的生成资源

实验设置

数据集

IEEE标准测试系统：

IEEE 13（2个源节点）
IEEE 18（2个源节点）
IEEE 33（3个源节点）

小世界网络：

WS 120（10个源节点）
WS 240（10个源节点）
WS 400（20个源节点）

评价指标

功率损耗：以千瓦(kW)为单位
计算时间：CPU执行时间(秒)
可行性：是否找到可行解

对比方法

Knitro：Artelys公司的商业MINLP求解器
传统MINLP方法：分支定界等精确算法

实现细节

平台：MacBook Air M3芯片，24GB RAM
编程语言：Julia
框架：PowerDistributionModel (PMD)
时间限制：3小时超时设置

实验结果

主要结果

网络	Knitro功率损耗(kW)	Knitro时间(s)	FORWARD功率损耗(kW)	FORWARD时间(s)
IEEE 13	360.183	4.189	360.183	0.033
IEEE 18	175.821	123.416	175.821	0.229
IEEE 33	318.568	3,345.67*	919.783	0.066
WS 120	TL	TL	1,428.72	0.361
WS 240	TL	TL	4,393.17	1.016
WS 400	TL	TL	28,345.7	3.090