A Heuristic Alternating Direction Method of Multipliers Framework for Distributed and Centralized Tree-Constrained Optimization: Applications to Hop-Constrained Spanning Tree Multicommodity Flow Design
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915844293918720 |
|---|---|
| author | Mokhtari, Yacine |
| author_facet | Mokhtari, Yacine |
| contents | 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 in many cases, achieving near-optimal performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11078 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Heuristic Alternating Direction Method of Multipliers Framework for Distributed and Centralized Tree-Constrained Optimization: Applications to Hop-Constrained Spanning Tree Multicommodity Flow Design Mokhtari, Yacine Optimization and Control 68R10, 68W10, 68W15, 90C11, 90C27, 90C30 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 in many cases, achieving near-optimal performance. |
| title | A Heuristic Alternating Direction Method of Multipliers Framework for Distributed and Centralized Tree-Constrained Optimization: Applications to Hop-Constrained Spanning Tree Multicommodity Flow Design |
| topic | Optimization and Control 68R10, 68W10, 68W15, 90C11, 90C27, 90C30 |
| url | https://arxiv.org/abs/2508.11078 |