Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2108.07549 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911117449625600 |
|---|---|
| author | Liu, Pengfei |
| author_facet | Liu, Pengfei |
| contents | This paper introduces a novel theoretical framework and a suite of highly efficient, parallelizable algorithms for solving the large-scale multicommodity flow (MCF) feasibility problem. We reframe the classical constraint-satisfaction problem as an equilibrium search. By defining vertex-specific height functions and edge-specific congestion functions, we establish a new, intuitive optimality condition: a flow is feasible if and only if it corresponds to a zero-stable pseudo-flow, where all potential differences across the network are resolved. This condition gives rise to an edge-separable convex optimization problem, whose structure is inherently suited for massive parallelization.
Based on this formulation, we develop a family of Potential Difference Reduction (PDR) algorithms. Our primary method, provably convergent, solves an exact quadratic programming subproblem for each edge in parallel. To address scenarios with a very large number of commodities, we propose two computationally cheaper heuristics based on adaptive gradient descent. Extensive numerical experiments on well-known benchmarks demonstrate the framework's remarkable performance. This work provides a powerful new approach for tackling large-scale MCF problems, while also identifying the formal analysis of the convergence rate as a promising direction for future research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_07549 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Localized Method for the Multi-commodity Flow Problem Liu, Pengfei Optimization and Control This paper introduces a novel theoretical framework and a suite of highly efficient, parallelizable algorithms for solving the large-scale multicommodity flow (MCF) feasibility problem. We reframe the classical constraint-satisfaction problem as an equilibrium search. By defining vertex-specific height functions and edge-specific congestion functions, we establish a new, intuitive optimality condition: a flow is feasible if and only if it corresponds to a zero-stable pseudo-flow, where all potential differences across the network are resolved. This condition gives rise to an edge-separable convex optimization problem, whose structure is inherently suited for massive parallelization. Based on this formulation, we develop a family of Potential Difference Reduction (PDR) algorithms. Our primary method, provably convergent, solves an exact quadratic programming subproblem for each edge in parallel. To address scenarios with a very large number of commodities, we propose two computationally cheaper heuristics based on adaptive gradient descent. Extensive numerical experiments on well-known benchmarks demonstrate the framework's remarkable performance. This work provides a powerful new approach for tackling large-scale MCF problems, while also identifying the formal analysis of the convergence rate as a promising direction for future research. |
| title | A Localized Method for the Multi-commodity Flow Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2108.07549 |