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 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 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».