Проблема потока мульти-товара является сетевым потоком проблемой с множеством товаров (требования потока) между различными узлами источника и раковиной.
Определение
Учитывая проточную сеть , где край имеет емкость . Есть товары , определяется , где а также является источником и раковина из товара, а также его спрос. Переменная определяет долю потока по краю , где в случае, если поток можно разделить на несколько путей, и в противном случае (например, «маршрутизация по одному пути»). Найдите назначение всех переменных потока, которое удовлетворяет следующим четырем ограничениям:
(1) Пропускная способность канала: сумма всех потоков, маршрутизируемых по каналу, не превышает его пропускной способности.
(2) Сохранение потока на транзитных узлах: количество потока, входящего в промежуточный узел. то же самое, что выходит из узла.
(3) Сохранение потока в источнике: поток должен полностью выходить из узла источника.
(4) Сохранение потока в пункте назначения: поток должен полностью войти в свой приемный узел.
Соответствующие задачи оптимизации
Балансировка нагрузки - это попытка направить потоки таким образом, чтобы использование всех ссылок четное, где
Проблема может быть решена, например, путем минимизации . Распространенной линеаризацией этой проблемы является минимизация максимального использования, где
В задаче о потоке нескольких товаров с минимальными затратами существует стоимость для отправки потока на . Затем вам нужно минимизировать
В задаче о максимальном потоке нескольких товаров спрос на каждый товар не является фиксированным, а общая пропускная способность максимизируется за счет максимизации суммы всех требований.
Отношение к другим проблемам
Вариант минимальной стоимости задачи многопродуктового потока является обобщением задачи минимальной стоимости потока (в которой есть только один источник и одна раковина . Варианты задачи циркуляции являются обобщением всех задач обтекания. То есть любую проблему потока можно рассматривать как конкретную проблему циркуляции. [1]
Применение
Маршрутизация и назначение длин волн (П) в оптической коммутации разрыва в оптической сети будет подходить по формулам потока нескольких товаров.
Решения
В варианте решения проблем, проблема получения целочисленного потока , удовлетворяющий все требования является NP-полным , [2] только две товаров и единичными мощности (делая проблему даже для сильно NP-полной в данном случае).
Если дробные потоки разрешен, то проблема может быть решена за полиномиальное время с помощью линейного программирования , [3] или через ( как правило , гораздо быстрее) полностью полиномиальная схемы приближения времени . [4]
Внешние ресурсы
- Документы Клиффорда Штайна об этой проблеме: 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 .; Итаи, А .; Шамир, А. (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 г.