A Heuristic ADMM-based Approach for Tree-Constrained Optimization
Yacine Mokhtari · 2025
Read A Heuristic ADMM-based Approach for Tree-Constrained Optimization by Yacine Mokhtari (2025) 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-2508-11078.txt.
Introduction
Yacine Mokhtari tackles network design problems with tree-shaped backbones in this 2025 paper. Many flow networks must ride on a spanning tree, a choice that explodes combinatorially. The test case limits how many hops each delivery may take across shared goods.
The method relaxes the yes-no choices into smooth values and glues them to a tree answer through a penalty scheme. Each round solves a smooth subproblem, then snaps the result to the cheapest valid tree, a fast classical step. A distributed twin lets agents cooperate by local messages alone. Experiments found near-best designs in many cases. The author frames the approach as a practical heuristic for large, hard design problems.
Catalog record
| CREATOR | Yacine Mokhtari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11078
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Heuristic ADMM-based Approach for Tree-Constrained Optimization Yacine Mokhtari Abstract This paper presents centralized and distributed Alternating Direction Method of Multipliers (ADMM) frameworks for solving large-scale nonconvex optimization problems with binary decision variables subject to spanning tree or rooted arborescence constraints. We address the combinatorial complexity by introducing a continuous relaxation of the binary variables and enforcing agreement through an augmented Lagrangian formulation. The algorithms alternate between solving a convex continuous subproblem and projecting onto the tree-feasible set, reducing to a Minimum Spanning Tree or Minimum Weight Rooted Arborescence problem, both solvable in polynomial time. The distributed algorithm enables agents to cooperate via local communication, enhancing scalability and robustness. We apply the framework to multicommodity flow design with hop-constrained spanning trees. Numerical experiments demonstrate that our methods yield high-quality feasible solutions, achieving near-optimal performance with significant computational savings compared to the commercial solver Gurobi. I Introduction I-A The Problem Let (\mathcal{V},\mathcal{E}) (resp. (\mathcal{V},\mathcal{A}) ) be an undirected (respectively directed) graph, where \mathcal{V} denotes the set of vertices and \mathcal{E}\subset\mathcal{V}\times\mathcal{V} (respectively \mathcal{A}\subset\mathcal{V}\times\mathcal{V} ) denotes the set of edges (resp. arcs). Throughout this work, we denote |\mathcal{V}|=n and |\mathcal{E}|=m (resp. ( |\mathcal{A}|=m )). Bold symbols consistently represent vectors or matrices; for example, if \boldsymbol{x}\in\mathbb{R}^{m} , then \boldsymbol{x}=(x_{1},x_{2},...,x_{m})^{T} . We consider the following Mixed-Integer Non-linear Programming (MINLP) problem: \begin{array}[]{ll}\text{minimize}&f\left(\boldsymbol{x},\boldsymbol{z}\right)\\[3.00003pt] \text{subject to}&g\left(\boldsymbol{x},\boldsymbol{z}\right)\leq\boldsymbol{0}_{q},\\[1.99997pt] &\left(\boldsymbol{x},\boldsymbol{z}\right)\in\mathcal{X}\times\mathcal{Z},\end{array} (1) where the continuous decision variable \boldsymbol{x}\in\mathbb{R}^{m} belongs to the set \mathcal{X}\subseteq\mathbb{R}^{m} , and \boldsymbol{z} is the binary decision variable in \mathcal{Z} indicating the activation status of the edges or arcs; that is, z_{ij}=1 if the edge or arc (i,j)\in\mathcal{E} or \mathcal{A} is active, and z_{ij}=0 otherwise. The number of constraints is denoted by q . A topological constraint is imposed on \boldsymbol{z} , requiring it to define either a spanning tree (in the undirected case) or a rooted arborescence (in the directed case) with a designated root node. Formally, \mathcal{Z}=\left\{\begin{array}[]{c}\boldsymbol{z}\in\{0,1\}^{m}:\boldsymbol{z}\ \text{induces a spanning tree}\\ \text{ or a rooted arborescence}\end{array}\right\}. We assume that both the objective function f:\mathcal{X}\times\tilde{\mathcal{Z}}\to\mathbb{R} and the constraint function g:\mathcal{X}\times\tilde{\mathcal{Z}}\to\mathbb{R}^{q} are jointly convex in their continuous arguments: (\boldsymbol{v},\boldsymbol{w})\mapsto f(\boldsymbol{v},\boldsymbol{w})\quad\text{and}\quad(\boldsymbol{v},\boldsymbol{w})\mapsto g(\boldsymbol{v},\boldsymbol{w}), are convex over \mathcal{X}\times\tilde{\mathcal{Z}} , where \tilde{\mathcal{Z}}=[0,1]^{m} denotes the convex hull of \mathcal{Z} . I-B Motivation and Applications Problem ( 1 ) addresses the design of network topologies that must satisfy both continuous operational constraints and discrete structural requirements; specifically, that the selected edges in the undirected case form a spanning tree, or, in the directed case, a rooted arborescence. In many real-world applications, additional structural and operational constraints further increase the problem’s complexity, leading to exponential growth with respect to the network size. For example, enforcing a maximum diameter or hop limit on the tree possibly in conjunction with multi-commodity flow requirements is essential in telecommunication and transportation networks, where bounded path lengths ensure acceptable latency and service quality [ 1 , 2 , 3 , 4 ] . In electric power systems, radial spanning-tree constraints are fundamental in distribution network reconfiguration problems, where the objective is to minimize power losses, balance loads, or improve reliability while preserving a radial topology for protection coordination and safe operation [ 5 , 6 , 7 , 8 , 9 , 10 ] . These diverse applications underscore the need for scalable algorithms capable of handling both centralized and distributed settings on directed or undirected graphs solving problem ( 1 ). I-C Solution Methods Problem ( 1 ) is a MINLP, for which both exact and approximate solution strategies exist. Among the exact approaches, the most direct method is complete enumeration , in which all feasible combinations of the discrete variables are systematically examined, the corresponding convex optimization subproblem is solved to optimality, and the configuration with the smallest objective value is retained. More sophisticated global methods include branch-and-bound [ 11 , 12 ] and branch-and-cut [ 13 , 14 ] , which guarantee identification of the global optimum. Cutting-plane techniques [ 15 , 16 ] iteratively solve relaxations of the original problem and add linear inequalities to progressively enforce integrality. While these methods provide theoretical guarantees, they typically have non-polynomial worst-case complexity, making them impractical for large-scale or embedded optimization, and their runtime can vary significantly across instances. Heuristic methods can quickly produce high-quality, though not necessarily optimal, solutions. Examples include the relax-and-round approach, which solves a convex relaxation and then projects the result onto the original nonconvex set, and approaches that fix nonconvex variables to plausible values before solving the remaining convex subproblems [ 17 ] . Feasibility-oriented heuristics, such as the feasibility pump [ 18 , 19 ] , aim to find feasible solutions efficiently. Although lacking theoretical guarantees, these methods are often effective in practice and well-suited to time-constrained settings. I-D The Alternating Direction Method The Alternating Direction Method of Multipliers (ADMM) is a primal–dual splitting algorithm originally developed for convex optimization problems [ 20 , 21 ] . Its use as a general heuristic for nonconvex optimization has been explored in, e.g., [ 20 , Ch. 9] and [ 22 ] , and it has recently attracted attention as a practical approach for obtaining approximate solutions to NP-hard problems. ADMM can address computationally challenging MINLPs [ 17 ] when projection onto the discrete constraint set can be performed, either exactly or approximately. While global convergence is not guaranteed in the nonconvex setting, ADMM often yields high-quality local solutions. ADMM has been successfully applied in various mixed-integer optimization contexts, including mixed-integer quadratic programming [ 23 ] , pump scheduling and water network management [ 24 ] , weighted network design with cardinality constraints [ 25 ] , and electric distribution system reconfiguration [ 6 , 9 , 10 ] . Its main strength lies in decomposing large-scale problems into simpler subproblems that can be solved sequentially while maintaining global coordination. This makes ADMM a scalable tool for centralized optimization tasks and a natural choice for designing distributed optimization algorithms that converge under mild assumptions [ 20 , 26 , 27 , 28 , 29 ] . I-E Distributed Optimization Distributed optimization encompasses a class of algorithms in which multiple agents cooperate to solve a global optimization problem. Such methods are valued for their scalability , robustness , privacy preservation , and adaptability . By partitioning the computational workload among agents, these algorithms are well-suited to large-scale systems, can tolerate local faults or communication losses, and alleviate centralized bottlenecks. For privacy-sensitive scenarios, distributed schemes enable local data processing without sharing raw information, thereby reducing both privacy risks and communication overhead compared to fully centralized architectures [ 27 , 26 ] . Applications span a wide range of domains, including networked multi-agent coordination, large-scale machine learning (e.g., distributed training of Support Vector Machines), and smart grid management [ 30 , 31 , 27 , 32 , 10 ] . A canonical formulation involves N agents jointly solving \underset{x\in\mathbb{R}^{N}}{\min}\ \sum_{i=1}^{N}f_{i}(x), (2) where f_{i}:\mathbb{R}^{N}\to\mathbb{R} denotes the local objective of agent i and x is a global decision variable shared by all agents. Although distributed optimization is well-developed for convex and continuous problems [ 33 ] , many practical settings, such as network reconfiguration, facility location, and scheduling, necessitate mixed-integer formulations with binary or general discrete variables. These distributed MINLPs are substantially more difficult due to their combinatorial nature, non-convex feasible