Многопродуктовые сетевые потоки (Multicommodity Flow Problem): маршрутизация и разделение емкостей

Математическая модель задачи многопродуктового потока (MCF) радикально усложняет классическую графовую оптимизацию. Задан ориентированный граф, каждое ребро которого имеет строго фиксированную глобальную пропускную способность (Capacity). Имеется K независимых продуктов (товаров или информационных пакетов), каждый из которых имеет свой собственный узел-исток, свой узел-сток и свой требуемый объем (Demand). Искомыми переменными являются величины потока каждого отдельного продукта на каждом отдельном ребре графа. Ограничения задачи делятся на две категории. Первая — строгий закон сохранения потока в узлах (для каждого продукта в отдельности!). Вторая — ограничение на совместную пропускную способность (Capacity Constraint): сумма потоков всех K продуктов, проходящих через любое конкретное ребро, не должна превышать глобальной пропускной способности этого ребра.

Именно это второе ограничение, связывающее все продукты воедино (Bundling Constraint), разрушает красивую структуру классической задачи о максимальном потоке. Из-за этого связывающего ограничения к многопродуктовой задаче абсолютно неприменима теорема о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона здесь бессилен, так как проталкивание одного продукта может заблокировать оптимальный путь для другого, создавая тупики, которые невозможно разрешить локальным поиском. Если переменные потока могут принимать непрерывные (дробные) значения, многопродуктовая задача решается методами классического линейного программирования. Однако из-за гигантского числа переменных и ограничений (равного числу ребер умноженному на число продуктов) стандартный симплекс-метод терпит крах.

Для обхода комбинаторного взрыва исследователи используют методы разложения (Decomposition), такие как метод Данцига-Вулфа или Лагранжева релаксация. Ограничения на совместную пропускную способность переносятся в целевую функцию с гигантскими штрафами (множителями Лагранжа). Это разрушает связь между продуктами, позволяя алгоритму находить кратчайшие пути для каждого из K продуктов абсолютно независимо (параллельно), а затем итеративно корректировать цены (штрафы) на перегруженных ребрах, пока система не придет к равновесию. Если задача требует целочисленных потоков (Integer Multicommodity Flow) — например, когда пакет данных нельзя разбить пополам или контейнер нельзя распилить — ситуация усложняется многократно.

Целочисленная задача MCF является сильно NP-трудной. Даже проверка существования допустимого пути для двух продуктов в направленном графе требует сложных комбинаторных эвристик. Для поиска решений аналитики применяют метод рандомизированного округления (Randomized Rounding). Сначала решается непрерывная (дробная) релаксация задачи. Полученные дробные потоки трактуются как вероятности. Затем компьютер случайным образом, опираясь на эти вероятности, округляет пути до целых значений. Математика строго доказывает (через границы Чернова), что при достаточном масштабе сети этот вероятностный подход дает целочисленное решение, фантастически близкое к идеальному непрерывному оптимуму. Сегодня алгоритмы многопродуктового потока являются мозгом концепции программно-определяемых сетей (SDN, Software-Defined Networking) в центрах обработки данных Google и Amazon, автоматически балансируя петабайты трафика между серверами, чтобы ни один кабель не оказался перегружен, в то время как другие простаивают.