Efficient Graph Partitioning under Resource Constraints: A Cutting-Plane Framework for Distribution Grids
Duong Thuy Anh Nguyen, Harsha Nagarajan, Robert Ferrando, Russell Bent, David Fobes · 2026
Read Efficient Graph Partitioning under Resource Constraints: A Cutting-Plane Framework for Distribution Grids by Duong Thuy Anh Nguyen, Harsha Nagarajan, Robert Ferrando, Russell Bent, David Fobes (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27180.txt.
Introduction
Nguyen and four colleagues build a network-layout control framework for splitting power grids under resource limits, using cutting-plane methods. The goal is live rearranging of linked subnetworks. Radial links, feasible resource flows, and a set leader plan must all hold. Those features support control spread across sites, stability, and teamwork. A mixed-integer program joins graph rules, resource flow, and network structure. Stepwise cuts handle cycle removal and leader choice until an optimal feasible layout is reached.
Catalog record
| CREATOR | Duong Thuy Anh Nguyen, Harsha Nagarajan, Robert Ferrando, Russell Bent, David Fobes |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48401 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27180
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Graph Partitioning under Resource Constraints: A Cutting-Plane Framework for Distribution Grids Duong Thuy Anh Nguyen, Harsha Nagarajan, Robert Ferrando, Russell Bent, David Fobes Abstract This paper presents an optimal network topology control framework using cutting-plane methods for efficient network partitioning with controllable edges. The objective is to enable real-time reconfiguration of interconnected sub-networks while ensuring radial connectivity, resource feasibility, and structured leader allocation, which are essential for distributed control, stability, and coordination. The problem is formulated as a mixed-integer program that integrates graph-theoretic constraints, resource flow, and network structural properties to enforce an operational hierarchy. To address the combinatorial complexity of cycle elimination and leader assignment, we propose an iterative cutting-plane framework that ensures convergence to an optimal and feasible network topology. Theoretical guarantees on optimality preservation, feasibility, and convergence are established, ensuring systematic elimination of infeasible configurations while maintaining distributed controllability. Simulations on a modified Iowa 240-bus power distribution grid demonstrate the framework’s effectiveness in network reconfiguration under resource constraints. The approach achieves median and best-case speedups of 57.5 × \times and over 64 × \times in a 46-switch configuration, highlighting its applicability to other networked control systems. I Introduction Network partitioning has long been recognized as a fundamental strategy of managing complexity in large-scale, interconnected systems such as power grids [ 8 ] , multi-agent systems [ 20 ] , and sensor networks [ 3 ] . By partitioning a global network into smaller, self-contained subnetworks, operators can localize control, optimize resource distribution, and effectively isolate critical infrastructure in response to emergencies or system overloads [ 4 , 19 , 13 ] . Motivated by the broad applicability of these strategies, this paper focuses on the optimal network partitioning problem. Despite the wide-ranging applications, achieving both optimality and scalability remains a fundamental challenge due to the combinatorial explosion from interdependent topological and operational decisions. In power distribution grids, ensuring each microgrid (a self-contained small-scale grid) remains acyclic (radial) leads to an exponential number of constraints even for moderate-sized systems [ 16 , 14 , 2 , 23 ] . Similarly, in multi-agent networks, forming stable coalitions that satisfy task requirements and communication constraints is known to be NP-hard [ 6 , 1 ] . While heuristic clustering protocols [ 3 , 24 ] reduce computational overhead; they often lack feasibility and performance guarantees. A common approach is to formulate a monolithic mixed-integer program (MIP) that explicitly encodes all constraints. While such monolithic formulations guarantee optimality in theory, they become computationally intractable as network size increase [ 9 ] . Enforcing topology properties like radiality can require an exponential number of cycle-prevention constraints [ 21 ] , and integrating resource allocation constraints further increases complexity [ 9 , 22 , 18 ] . Early reconfiguration methods [ 4 , 17 ] and subsequent advances in multi-commodity flow [ 14 ] or sub-tour elimination [ 2 ] remain limited by exponential growth in binary variables [ 6 , 21 ] . Given this intractability, metaheuristic local search algorithms (e.g., genetic algorithms [ 10 ] , particle swarm or local search) are often employed. However, these methods often rely on problem-specific parameter tuning and heuristics without rigorous optimality or feasibility guarantees for complex constraints. Consequently, there remains a critical need for scalable methods that are either exact or provably near-optimal , and can systematically integrate the full spectrum of constraints in modern network problems. In recent years, decomposition-based methods, particularly cutting-plane algorithms, have garnered significant interest for high-dimensional MIPs [ 15 , 21 , 9 ] . By generating constraints only to exclude detected infeasibilities, such as cycles or subnetworks with insufficient resources, iterative frameworks often achieve substantial computational speed-ups compared to monolithic formulations [ 5 , 15 , 11 ] . However, their application to integrated network partitioning with complex inter-dependencies between topological and operational constraints remains relatively underexplored. Motivated by these limitations, this paper introduces a novel cutting-plane framework for fast, optimal network partitioning that integrates topological, resource, and hierarchical constraints. To address the combinatorial complexity of these requirements, we present a comprehensive set of mixed-integer linear constraints, leveraging a directed multi-commodity flow-based approach [ 14 ] to enforce radiality and a coloring-based method [ 12 ] to ensure the correct assignment of hierarchy within subnetworks. Although these formulations provide a rigorous mathematical foundation, their direct implementation results in computationally expensive optimization, especially as network size increases. Our key contribution is an iterative cutting-plane algorithm that enforces these constraints dynamically. We develop novel cutting-plane constraints (or cuts) that systematically and efficiently refine the solution space. The algorithm begins by solving a relaxed partitioning model. If infeasibilities are detected, appropriate cutting-plane constraints are dynamically introduced in subsequent iterations. Notably, we formally establish theoretical guarantees that the proposed algorithm converges to the same optimal solution as the full monolithic MIP but with significantly reduced computational effort. Contributions are summarized as follows. (i) We introduce a cutting-plane framework for optimal network partitioning integrating graph-theoretic constraints, resource flow, and structured leader allocation to enable reconfiguration while ensuring topological and operational feasibility. (ii) We develop novel iterative cutting-plane constraints that dynamically enforce cycle elimination and leader assignment, significantly reducing computational complexity versus monolithic MIPs. (iii) We theoretically guarantee optimality, feasibility, and convergence. (iv) We validate the framework via simulations on an Iowa 240-bus power systems application. II Network Model Consider a network represented as a directed graph \mathbb{G}=(\mathcal{N},\mathcal{E}) , where \mathcal{N}=\{1,2,\dots,N\} is the set of nodes, representing individual components such as devices, agents, subsystems, or entities. The set of edges \mathcal{E}\subseteq\mathcal{N}\times\mathcal{N} represents the connections between nodes, which may include communication links, physical connections, power lines, or transportation pathways. Each edge (i,j)\in\mathcal{E} is oriented from node i to node j , indicating the permissible direction of flow, whether it be data, power, or other resources. A subset of \mathcal{E} , denoted by \mathcal{E}^{\mathrm{sw}}\subseteq\mathcal{E} , comprises the controllable edges whose open/closed state can be selected to partition the network into sub-networks. An undirected network is a special case of this formulation, where each connection is bidirectional. The network structure is illustrated in Fig 1 . Fig. 1 : Prototype network. This paper addresses optimal network reconfiguration by controlling \mathcal{E}^{\mathrm{sw}} to achieve target topology and functionality. Such adaptive partitioning allows the network to transition between topological states, which is is critical for power grids, multi-agent systems, and distributed computing. II-A Base Blocks Define \mathcal{B} as the set of disjoint base blocks \ell\in\mathcal{B} . Each block represents the smallest predefined sub-network, a subset of nodes that remains connected when all controllable edges are open. To model the activation state of each base block \ell\in\mathcal{B} , we introduce the binary decision variable: \displaystyle z^{\mathrm{bl}}_{\ell}=\begin{cases}1,&\text{if block }\ell\in\mathcal{B}\text{ is active},\\ 0,&\text{otherwise}.\end{cases} (1) Here, z^{\mathrm{bl}}_{\ell}=1 indicates that the constituent nodes of block \ell are operational and functional within the network. II-B Controllable Edges The subset \mathcal{E}^{{\text{sw}}}\subseteq\mathcal{E} denotes controllable edges (or “switches”) that enable network reconfiguration. For each controllable edge (i,j)\in\mathcal{E}^{\mathrm{sw}} , we define a decision variable: \displaystyle z_{ij}^{\mathrm{sw}}=\begin{cases}1,&\text{if the edge is closed (active)},\\ 0,&\text{if the edge is open}.\end{cases} (2) Closing a switch ( z_{ij}^{\mathrm{sw}}=1 ) merges base blocks into larger connected components , defined as maximal subsets of nodes where every pair is linked by a sequence of active edges. Conversely,