Статьи автора

РЕШЕНИЕ ЗАДАЧ О МНОГОТОВАРНЫХ СЕТЕВЫХ ПОТОКАХ БОЛЬШОЙ РАЗМЕРНОСТИ НА ГРАФИЧЕСКИХ ПРОЦЕССОРАХ

Номер выпуска 8 от 01.08.2025

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

1 0