Accelerated method improves linear constraint solving on dynamic graphs
AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs
Machine LearningArtificial Intelligence
Summary
Solving problems with many strict rules on large networks can be very slow and costly. The authors created a faster approach that focuses only on the most important parts of the problem and updates calculations efficiently when the network changes. Their method speeds up solving by up to seven times while still perfectly following all the rules. It works well on problems like power grid security and gas transport optimization. This helps computers solve complex network problems more quickly and reliably.
What this means in practice
- •For energy grid operators: Improve real-time security checks for power grid operations with faster constraint solving on evolving network states.
- •For gas pipeline managers: Speed up optimization of gas transport networks while ensuring strict safety and operation constraints are met exactly.
Authors
Xiaochen Zhang, Haoyu Zhu, Yao Zhang, Qingchun Hou
Abstract
Graph-structured optimization with linear constraints is fundamental to critical infrastructure but faces scalability limits due to massive strict hard constraints and high dimensionality. While recent projection-based methods such as Trainable Sampling Kaczmarz-Motzkin Net (T-SKM-Net) guarantee feasibility, they face high computational costs in dynamic environments by processing the entire constraint set and requiring expensive matrix factorizations. To bridge this gap, we propose the Accelerated Trainable-SKM (AT-SKM) Net framework. To concentrate computation on the active constraints and eliminate redundant calculations, we introduce a hybrid sampling strategy guided by a topology-aware heterogeneous GNN model. To efficiently handle topological shifts in graph-based constraints, we employ a Cholesky Update mechanism that theoretically reduces the equality projection complexity from O(N^3) to O(N^2) under low-rank perturbations. Experiments on random geometric graphs, N-1 Security-Constrained DC-OPF, and minimum-cost gas transport problem demonstrate that AT-SKM reduces iteration counts by up to 85% and achieves 2.95x-7.29x SKM layer speedups, while maintaining zero constraint violations.