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

Задача сетевого потока (математика)

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

Определение

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

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

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

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

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

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

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

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

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

Соответствующие задачи оптимизации

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

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

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

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

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

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

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

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

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

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

Маршрутизация и распределение длин волн (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/

Ссылки

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

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