Проблема многотоварного потока

Проблема многотоварного потока — это проблема сетевого потока с несколькими товарами (потребностями потока) между разными узлами-источниками и узлами-приемниками.

Определение

Учитывая сеть потоков $\,G(V,E)$ , где край $(u,v)\in E$ имеет емкость $\,c(u,v)$ . Есть $\,k$ товары $K_{1},K_{2},\dots ,K_{k}$ , определяемый $\,K_{i}=(s_{i},t_{i},d_{i})$ , где $\,s_{i}$ и $\,t_{i}$ является источником и поглотителем товара $\,i$ , и $\,d_{i}$ это его требование. Переменная $\,f_{i}(u,v)$ определяет долю потока $\,i$ вдоль края $\,(u,v)$ , где $\,f_{i}(u,v)\in [0,1]$ в случае, если поток можно разделить между несколькими путями, и $\,f_{i}(u,v)\in \{0,1\}$ в противном случае (т.е. «маршрутизация по одному пути»). Найдите назначение всех переменных потока, которое удовлетворяет следующим четырем ограничениям:

(1) Пропускная способность канала: сумма всех потоков, маршрутизируемых по каналу, не превышает его пропускную способность.

\forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)

(2) Сохранение потока на транзитных узлах: объем потока, поступающего в промежуточный узел. $u$ то же самое, что выходит из узла.

\forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(u,w)-\sum _{w\in V}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}

(3) Сохранение потока в источнике: поток должен полностью покинуть исходный узел.

\forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1

(4) Сохранение потока в пункте назначения: поток должен полностью войти в узел стока.

\forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(w,t_{i})-\sum _{w\in V}f_{i}(t_{i},w)=1

Соответствующие проблемы оптимизации

Балансировка нагрузки — это попытка маршрутизировать потоки таким образом, чтобы использование $U(u,v)$ из всех ссылок $(u,v)\in E$ четно, где

U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}

Проблему можно решить, например, минимизировав $\sum _{u,v\in V}(U(u,v))^{2}$ . Общей линеаризацией этой задачи является минимизация максимального использования. $U_{max}$ , где

\forall (u,v)\in E:\,U_{max}\geq U(u,v)

В задаче о многотоварном потоке с минимальной стоимостью существует стоимость $a(u,v)\cdot f(u,v)$ для отправки потока на $\,(u,v)$ . Затем вам нужно минимизировать

\sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)

В задаче о максимальном многотоварном потоке спрос на каждый товар не фиксирован, а общая пропускная способность максимизируется за счет максимизации суммы всех потребностей. $\sum _{i=1}^{k}d_{i}$

Связь с другими проблемами

Вариант минимальных затрат задачи многотоварного потока является обобщением задачи о потоке минимальных затрат (в которой имеется только один источник $s$ и одна раковина $t$ ). Варианты задачи циркуляции являются обобщением всех задач о потоке. То есть любую проблему потока можно рассматривать как конкретную задачу циркуляции. ^[1]

Использование

Маршрутизация и присвоение длины волны (RWA) при коммутации оптических пакетов в оптической сети будут осуществляться с помощью формул многопродуктового потока.

Распределение регистров можно смоделировать как задачу целочисленного многопродуктового потока с минимальной стоимостью: значения, создаваемые инструкциями, являются исходными узлами, значения, потребляемые инструкциями, являются узлами приемников, а регистры, а также слоты стека являются ребрами. ^[2]

Решения

В версии решения задачи задача создания целочисленного потока, удовлетворяющего всем требованиям, является NP-полной , ^[3] даже только для двух товаров и единичных мощностей (что делает задачу в этом случае строго NP-полной ).

Если разрешены дробные потоки, проблема может быть решена за полиномиальное время с помощью линейного программирования . ^[4] или с помощью (обычно гораздо более быстрых) полностью полиномиальных схем аппроксимации времени . ^[5]

Приложения

Многопродуктовый поток применяется в наложенной маршрутизации при доставке контента. ^[6]

Внешние ресурсы

Статьи Клиффорда Стайна об этой проблеме: http://www.columbia.edu/~cs2035/papers/#mcf
Программное обеспечение, решающее проблему: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Ссылки

^ Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки. Теория, алгоритмы и приложения . Прентис Холл.
^ Коес, Дэвид Райан (2009). «На пути к более принципиальному компилятору: новый взгляд на распределение регистров и выбор инструкций» (доктор философии). Университет Карнеги-Меллон. S2CID 26416771 .
^ С. Эвен, А. Итай и А. Шамир (1976). «О сложности расписания и проблем многотоварных потоков». SIAM Journal по вычислительной технике . 5 (4). СИАМ: 691–703. дои : 10.1137/0205048 . Эвен, С.; Итай, А.; Шамир, А. (1975). «О сложности расписания и задач многотоварных потоков». 16-й ежегодный симпозиум по основам информатики (SFCS, 1975) . стр. 184–193. дои : 10.1109/SFCS.1975.21 . S2CID 18449466 .
^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2009). «29». Введение в алгоритмы (3-е изд.). MIT Press и МакГроу-Хилл. п. 862. ИСБН 978-0-262-03384-8 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Георгий Каракостас (2002). «Схемы более быстрой аппроксимации для задач дробного многопродуктового потока» . Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 166–173 . ISBN 0-89871-513-Х .
^ Алгоритмические самородки в доставке контента sigcomm.org

Добавить: Жан-Патрис Неттер, Сети, увеличивающие поток: основной тип подхода к максимальному целочисленному потоку в многопродуктовой сети, докторская диссертация Университета Джона Хопкинса, 1971 г.

[ahuja_et_al_1993-1] Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки. Теория, алгоритмы и приложения . Прентис Холл.

[2] Коес, Дэвид Райан (2009). «На пути к более принципиальному компилятору: новый взгляд на распределение регистров и выбор инструкций» (доктор философии). Университет Карнеги-Меллон. S2CID 26416771 .

[EIS76-3] С. Эвен, А. Итай и А. Шамир (1976). «О сложности расписания и проблем многотоварных потоков». SIAM Journal по вычислительной технике . 5 (4). СИАМ: 691–703. дои : 10.1137/0205048 . Эвен, С.; Итай, А.; Шамир, А. (1975). «О сложности расписания и задач многотоварных потоков». 16-й ежегодный симпозиум по основам информатики (SFCS, 1975) . стр. 184–193. дои : 10.1109/SFCS.1975.21 . S2CID 18449466 .

[4] Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн (2009). «29». Введение в алгоритмы (3-е изд.). MIT Press и МакГроу-Хилл. п. 862. ИСБН 978-0-262-03384-8 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Георгий Каракостас (2002). «Схемы более быстрой аппроксимации для задач дробного многопродуктового потока» . Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 166–173 . ISBN 0-89871-513-Х .

[6] Алгоритмические самородки в доставке контента sigcomm.org

[1]

[2]

[3]

[4]

[5]

[6]