Проблема многопродуктового потока - Multi-commodity flow problem

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

Определение

Дана проточная сеть , где у края есть пропускная способность . Есть товары , определяемые тем , где и является источником и приемником товара , а также его спросом. Переменная определяет долю потока по краю , где в случае, если поток может быть разделен между несколькими путями, и в противном случае (например, «маршрутизация по одному пути»). Найдите присвоение всех переменных потока, которое удовлетворяет следующим четырем ограничениям: ${\ Displaystyle \, G (V, E)}$ ${\ displaystyle (u, v) \ in E}$ ${\ Displaystyle \, с (и, v)}$ ${\ displaystyle \, k}$ ${\ displaystyle K_ {1}, K_ {2}, \ dots, K_ {k}}$ ${\ displaystyle \, K_ {i} = (s_ {i}, t_ {i}, d_ {i})}$ ${\ displaystyle \, s_ {i}}$ ${\ Displaystyle \, т_ {я}}$ ${\ Displaystyle \, я}$ ${\ displaystyle \, d_ {i}}$ ${\ Displaystyle \, е_ {я} (и, v)}$ ${\ Displaystyle \, я}$ ${\ Displaystyle \, (и, v)}$ ${\ Displaystyle \, е_ {я} (и, v) \ в [0,1]}$ ${\ Displaystyle \, е_ {я} (и, v) \ в \ {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 я \ в К: \, \ сумма _ {ш \ в V} е_ {я} (и, ш) - \ сумма _ {ш \ в V} е_ {я} (ш, и) = 0 \ quad \ mathrm {когда} \ quad u \ neq s_ {i}, t_ {i}}

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

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

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

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

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

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

{\ Displaystyle U (u, v) = {\ гидроразрыва {\ sum _ {i = 1} ^ {k} f_ {i} (u, v) \ cdot d_ {i}} {c (u, v)} }}

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

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

В задаче о потоке нескольких товаров с минимальными затратами существует стоимость отправки потока . Затем вам нужно минимизировать ${\ Displaystyle а (и, v) \ cdot f (и, v)}$ ${\ Displaystyle \, (и, v)}$

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

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

Отношение к другим проблемам

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

Применение

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

Решения

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

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

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

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

Рекомендации

^ Ахуджа, Равиндра К .; Magnanti, Thomas L .; Орлин, Джеймс Б. (1993). Сетевые потоки. Теория, алгоритмы и приложения . Прентис Холл.
^ С. Эвен, А. Итаи и А. Шамир (1976). «О сложности расписания и проблем многопродуктовых потоков». SIAM Journal on Computing . СИАМ. 5 (4): 691–703. DOI : 10.1137 / 0205048 . Даже, S .; Itai, A .; Шамир, А. (1975). «О сложности расписания и проблем многопродуктовых потоков». 16-й ежегодный симпозиум по основам информатики (SFCS 1975) . С. 184–193. DOI : 10,1109 / SFCS.1975.21 .
^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн (2009). «29». Введение в алгоритмы (3-е изд.). MIT Press и McGraw – Hill. п. 862. ISBN 978-0-262-03384-8 . CS1 maint: несколько имен: список авторов ( ссылка )
^ Джордж Каракостас (2002). «Схемы более быстрой аппроксимации для дробных задач многопродуктового потока» . Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С. 166–173 . ISBN 0-89871-513-X .

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

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

[EIS76-2] С. Эвен, А. Итаи и А. Шамир (1976). «О сложности расписания и проблем многопродуктовых потоков». SIAM Journal on Computing . СИАМ. 5 (4): 691–703. DOI : 10.1137 / 0205048 . Даже, S .; Itai, A .; Шамир, А. (1975). «О сложности расписания и проблем многопродуктовых потоков». 16-й ежегодный симпозиум по основам информатики (SFCS 1975) . С. 184–193. DOI : 10,1109 / SFCS.1975.21 .

[3] Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн (2009). «29». Введение в алгоритмы (3-е изд.). MIT Press и McGraw – Hill. п. 862. ISBN 978-0-262-03384-8 . CS1 maint: несколько имен: список авторов ( ссылка )

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

Languages

In other projects