REShENIE ZADACh O MNOGOTOVARNYKh SETEVYKh POTOKAKh BOL'ShOY RAZMERNOSTI NA GRAFIChESKIKh PROTsESSORAKh

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Рассматривается задача о многотоварных сетевых потоках из всех пар узлов в сети с ребрами, имеющими заданные пропускные способности. При обычном подходе для каждой пары узлов “источник–назначение” на каждом ребре отслеживается отдельный поток. В статье используется более эффективная формулировка, в которой потоки с одним и тем же узлом-назначением объединяются, что позволяет уменьшить количество переменных в k раз, где k – размер сети. Задачи с сотнями узлов, с общим числом переменных порядка миллиона, могут быть решены стандартными общими методами внутренней точки на центральных процессорах (CPU); ниже используются совместимые с графическими процессорами (GPU) алгоритмы, которые могут решать такие задачи гораздо быстрее и, кроме того, масштабируются на гораздо большие задачи, с миллиардом переменных. Представленный метод основан на прямо-двойственном гибридном градиентном алгоритме и использует несколько особенностей задачи для эффективных вычислений на GPU. С помощью численных экспериментов показано, что прямо-двойственный метод многотоварных сетевых потоков ускоряет современные коммерческие решатели от 100 до 1000 раз и масштабируется на задачи гораздо большего размера. Приведена реализация данного метода с открытым исходным кодом.

About the authors

F. ChZhAN

Email: zfzhao@stanford.edu

S. BOYD

Email: boyd@stanford.edu

References

  1. Yin P., Diamond S., Lin B., Boyd. S. Network optimization for unified packet and circuit switched networks // ArXiv Preprint ArXiv:1808.00586. 2019. https://arxiv.org/abs/1808.00586
  2. Bar-Gera H., Boyce D. Origin-based algorithms for combined travel forecasting models // Transportation Research Part B: Methodological. 2003. V. 37. No. 5. P. 405–422.
  3. Boyd S., Vandenberghe L. Convex Optimization. Cambridge: Cambridge University Press, 2004.
  4. ApS MOSEK. The MOSEK optimization toolbox for MATLAB manual. Version 9.0. 2019. http://docs.mosek.com/9.0/toolbox/index.html
  5. Diamond S., Boyd S. CVXPY: A Python-embedded modeling language for convex optimization // J. Machin. Learn. Res. 2016. V. 17. No. 83. P. 1–5.
  6. Ford Jr.L., Fulkerson D. A suggested computation for maximal multi-commodity network flows // Management Science. 1958. V. 5. No. 1. P. 97–101.
  7. Hu T. Multi-commodity network flows // Operations Research. 1963. V. 11. No. 3. P. 344–360.
  8. Gautier A., Granot F. Forest management: A multicommodity flow formulation and sensitivity analysis // Management Science. 1995. V. 41. No. 10. P. 1654–1668.
  9. Ouorou A., Mahey P. A minimum mean cycle cancelling method for nonlinear multicommodity flow problems // Eur. J. Oper. Res. 2000. V. 121. No. 3. P. 532–548.
  10. Manfren M. Multi-commodity network flow models for dynamic energy management–mathematical formulation // Energy Procedia. 2012. V. 14. P. 1380–1385.
  11. Kabadurnus O., Smith A. Multi-commodity k-splittable survivable network design problems with relays // Telecommunication Systems. 2016. V. 62. P. 123–133.
  12. Zantuti A. The capacity and non-simultaneously multicommodity flow problem in wide area network and data flow management // Proceedings of the 18th International Conference on Systems Engineering. 2005. P. 76–80. https://doi.org/10.1109/ICSENG.2005.81
  13. Erera A., Morales J., Savelsbergh M. Global intermodal tank container management for the chemical industry // Transportation Research Part E: Logistics and Transportation Review. 2005. V. 41. P. 551–566.
  14. Mesquita M., Moz M., Paias A., Pato M. A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern // European Journal of Operational Research. 2015. V. 245. No. 2. P. 423–437.
  15. Rudi A., Frohling M., Zimmer K., Schultmann F. Freight transportation planning considering carbon emissions and in-transit holding costs: a capacitated multicommodity network flow model // EURO J. Transport. Logist. 2016. V. 5. P. 123–160. https://api.semanticscholar.org/CorpusID:53229695
  16. Singh I. A dynamic multi-commodity model of the agricultural sector: A regional application in Brazil // European Economic Review. 1978. V. 11. P. 155–179. https://api.semanticscholar.org/CorpusID:152973282
  17. Wagner D., Raúll G., Pferschy U., Mutzel P., Bachhtesl P. A multi-commodity flow approach for the design of the last mile in real-world fiber optic networks // Operation Research Proceedings. 2006. https://api.semanticscholar.org/CorpusID:17037020
  18. Layeb S., Heni R., Balma A. Compact MILP models for the discrete cost multicommodity network design problem // 2017 International Conference on Engineering & MIS. IEEE, 2017. P. 1–7.
  19. Salimifard K., Bigharaz S. The multicommodity network flow problem: state of the art classification, applications, and solution methods // Operational Research. 2022. V. 22. No. 1. P. 1–47.
  20. Ovorou A., Mahey P., Vial J. A survey of algorithms for convex multicommodity flow problems // Management Science. 2000. V. 46. No. 1. P. 126–147.
  21. Liu X., Arzani B., Kokarla S., Zhao L., Liu V., Castro M., Kandula S., Marshall L. Rethinking machine learning collective communication as a multi-commodity flow problem // Proceedings of the ACM SIGCOMM 2024 Conference. 2024. P. 16–37.
  22. Basu P., Zhao L., Fanti J., Pal S., Krishnamurthy A., Khoury J. Efficient all-to-all collective communication schedules for direct-connect topologies // Proceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing. 2024. P. 28–41. https://doi.org/10.1145/3625549.3658656
  23. Applegate D., Díaz M., Hinder O., Lu H., Lubin M., O’Donoghue B., Schudy W. Practical large-scale linear programming using primal-dual hybrid gradient // Neural Information Processing Systems. 2021. https://api.semanticscholar.org/CorpusID:235376806
  24. Lu H., Yang J. cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia // ArXiv Preprint ArXiv:2311.12180. 2024. https://arxiv.org/abs/2311.12180
  25. Lu H., Peng Z., Yang J. MPAX: mathematical programming in JAX // ArXiv Preprint ArXiv:2412.09734. 2024. https://arxiv.org/abs/2412.09734
  26. Ryu E., Chen Y., Li W., Osher S. Vector and matrix optimal mass transport: theory, algorithm, and applications // SIAM J. Scientif. Comput. 2018. V. 40. No. 5. P. A3675-A3698.
  27. Degleris A., Gamal A., Rajagopal R. GPU accelerated security constrained optimal power flow // ArXiv Preprint ArXiv:2410.17203. 2024. https://arxiv.org/abs/2410.17203
  28. Ryu M., Byeon G., Kim K. A GPU-accelerated distributed algorithm for optimal power flow in distribution systems // ArXiv Preprint ArXiv:2501.08293. 2025.
  29. Wang X., Zhang Q., Ren J., Xu S., Wang S., Yu S. Toward efficient parallel routing optimization for large-scale SDN networks using GPGPU // Journal Network Comput. Appl. 2018. V. 113. P. 1–13.
  30. Kikuta K., Oki E., Yamanaka N., Togawa N., Nakazato H. Effective parallel algorithm for GPGPU-accelerated explicit routing optimization // 2015 IEEE Global Communications Conference. IEEE, 2015. P. 1–6.
  31. Zhang S., Ajayi O., Cheng Y. A self-supervised learning approach for accelerating wireless network optimization // IEEE Transactions on Vehicular Technology. 2023. V. 72. No. 6. P. 8074–8087.
  32. Wu J., He Z., Hong B. Chapter 5 – Efficient CUDA algorithms for the maximum network flow problem // GPU Computing Gems Jade Edition. Boston: Morgan Kaufmann, 2012. P. 55–66. https://www.sciencedirect.com/science/article/pii/B9780123859631000058
  33. Liu H., Huang S., Qin S., Yang T., Yang T., Xiang Q., Liu X. Keep your paths free: Toward scalable learning-based traffic engineering // Proceedings of the 8th Asia-Pacific Workshop on Networking. 2024. P. 189–191. https://doi.org/10.1145/3663408.3665813
  34. Gurobi Optimization. LLC Gurobi Optimizer Reference Manual. 2024. https://www.gurobi.com
  35. Yarmoshik D., Persitanov M. On the application of saddle-point methods for combined equilibrium transportation models // Proceedings of the 23rd International Conference on Mathematical Optimization Theory and Operations Research (MOTOR). 2024. P. 432–448. https://doi.org/10.1007/978-3-031-62792-7_29
  36. Kubentayeva M., Yarmoshik D., Persitanov M., Kroshnin A., Kotliarova E., Tuptisa N., Pasechnyuk D., Gasnikov A., Shvetsov V., Baryshev L., Shurypov A. Primal-dual gradient methods for searching network equilibria in combined models with nested choice structure and capacity constraints // ArXiv Preprint ArXiv:2307.00427. 2023. https://arxiv.org/abs/2307.00427
  37. Malitsky Y., Pock T. A first-order primal-dual algorithm with linesearch // SIAM J. Optim. 2018. V. 28. No. 1. P. 411–432.
  38. Zhu M., Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restoration // UCLA CAM Report. 2008. V. 34. No. 2.
  39. Chambolle A., Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging // J. Math. Imaging Vision. 2011. V. 40. P. 120–145.
  40. Chambolle A., Pock T. On the ergodic convergence rates of a first-order primal-dual algorithm // Mathematical Programming. 2015. V. 159. P. 253–287.
  41. Parikh N., Boyd S. Proximal algorithms // Foundations and Trends in Optimization. 2014. V. 1. No. 3. P. 127–239.
  42. Held M., Wolfe P., Crowder H. Validation of subgradient optimization // Mathematical Programming. 1974. V. 6. P. 62–88.
  43. Duchi J., Shalev-Shwartz S., Singer Y., Chandra T. Efficient projections onto the l1-ball for learning in high dimensions // Proceedings of the 25th International Conference on Machine Learning. 2008. P. 272–279. https://doi.org/10.1145/1390156.1390191
  44. Condat L. Fast projection onto the simplex and the l1 ball // Mathematical Programming. 2016. V. 158. No. 1-2. P. 575–585. https://doi.org/10.1007/s10107-015-0946-6

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 The Russian Academy of Sciences