Large-Scale Network Utility Maximization via GPU-Accelerated Proximal Message Passing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911152673390592 |
|---|---|
| author | Sreekumar, Akshay Degleris, Anthony Rajagopal, Ram |
| author_facet | Sreekumar, Akshay Degleris, Anthony Rajagopal, Ram |
| contents | We present a GPU-accelerated proximal message passing algorithm for large-scale network utility maximization (NUM). NUM is a fundamental problem in resource allocation, where resources are allocated across various streams in a network to maximize total utility while respecting link capacity constraints. Our method, a variant of ADMM, requires only sparse matrix-vector multiplies with the link-route matrix and element-wise proximal operator evaluations, enabling fully parallel updates across streams and links. It also supports heterogeneous utility types, including logarithmic utilities common in NUM, and does not assume strict concavity. We implement our method in PyTorch and demonstrate its performance on problems with tens of millions of variables and constraints, achieving 4x to 20x speedups over existing CPU and GPU solvers and solving problem sizes that exhaust the memory of baseline methods. Additionally, we show that our algorithm is robust to congestion and link-capacity degradation. Finally, using a time-expanded transit seat allocation case study, we illustrate how our approach yields interpretable allocations in realistic networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10722 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Large-Scale Network Utility Maximization via GPU-Accelerated Proximal Message Passing Sreekumar, Akshay Degleris, Anthony Rajagopal, Ram Optimization and Control Networking and Internet Architecture Systems and Control We present a GPU-accelerated proximal message passing algorithm for large-scale network utility maximization (NUM). NUM is a fundamental problem in resource allocation, where resources are allocated across various streams in a network to maximize total utility while respecting link capacity constraints. Our method, a variant of ADMM, requires only sparse matrix-vector multiplies with the link-route matrix and element-wise proximal operator evaluations, enabling fully parallel updates across streams and links. It also supports heterogeneous utility types, including logarithmic utilities common in NUM, and does not assume strict concavity. We implement our method in PyTorch and demonstrate its performance on problems with tens of millions of variables and constraints, achieving 4x to 20x speedups over existing CPU and GPU solvers and solving problem sizes that exhaust the memory of baseline methods. Additionally, we show that our algorithm is robust to congestion and link-capacity degradation. Finally, using a time-expanded transit seat allocation case study, we illustrate how our approach yields interpretable allocations in realistic networks. |
| title | Large-Scale Network Utility Maximization via GPU-Accelerated Proximal Message Passing |
| topic | Optimization and Control Networking and Internet Architecture Systems and Control |
| url | https://arxiv.org/abs/2509.10722 |