Comments 8
Там где у вас формула для целевой функции L() у вас неточность в нотации. Сумма по переменной i, означающей ребро, а внутри u_ij, но вот это i внутри - это уже узел, а не ребро. Правильно было бы записать сумму по 1 <= i,j <=n, Где n - количество узлов. Но это мелочь, просто в глаза бросилось.
А вопрос по делу: как работает оптимизация, что за решатель? У вас линейные ограничения, но целевая функция не линейная и даже не квадратичная. Как должно оно работает?
Кажется, вашу задачу можно свести к задаче линейного программирования, если все потоки и ограничения сделать целыми. Вроде как пропускная способность бит/с и потоки тоже в неделимых битах/с считать. Тогда можно разбить каждое ребро с пропускной способностью C на кучу параллельных ребер с пропускными способностями 1 бит/c и назначить им цены: 0/C-1/(C-1), 2/(C-2) - 1/(C-1)... ,(C-1)/1- (C-2)/2. Фактически, цена ребра - это разность L(k)-L(k-1) - на сколько увеличится штраф по изначальному ребру, если по нему пустить дополнительную единицу потока, пока там уже было k-1 потока. Поскольку целевая функция выпуклая от полного потока по ребру, то приращения строго возрастают при увеличении потока, поэтому просто взяв k минимальных параллельных ребер вы получите точно целевую функцию при потоке k по изначальному ребру. И вот уже задача свелась к мульти-потоку в графе. Тут уже линейные решатели (при чем даже не целочисленные) все решат, возможно даже быстрее. А если поток всего один, то задача вообще за полиномиальное время решается.
С другой стороны, это сильно увеличивает количество ребер в графе. Но тут можно балансировать точность и скорость. Если считать не в бит/c а кбит/c или 100кбит/c, то вы уменьшаете количество параллельных ребер и ускоряете решение.
Гуглите в сторону выпуклых целевых функций для максимального потока в графе.
В качестве основного инструмента используется Ipopt (Interior Point OPTimizer) - пакет для решения задач нелинейной оптимизации с ограничениями. Он не требует линейности или квадратичности целевой функции, а работает с произвольными гладкими функциями. Целевая функция является гладкой и выпуклой на допустимой области. JuMP автоматически вычисляет её градиент и гессиан и передаёт их Ipopt. Тот методом внутренней точки ищет глобальный минимум, последовательно приближаясь к оптимальному значению изнутри допустимой области. Ограничения действительно линейные: уравнения баланса потоков в узлах и неравенства (интенсивности не могут превышать пропускную способность узлов). Это стандартная задача выпуклой оптимизации, и Ipopt решает её гарантированно, упираясь в локальный минимум.
Таким образом, представленный алгоритм
У вас нет алгоритма как такового на самом деле. У вас формулировка задачи для решателя. Да, там n^2m переменных и очень много ограничений, и их надо циклами сгенерировать, но это не очень достойно гордого названия "алгоритм".
Математическая формулировка - это тоже работа и это стоит статьи, но я бы не называл это алгоритмом.
Алгоритм - это точная последовательность действий, которая позволяет решить задачу или достичь определённого результата.
В инженерной практике алгоритм это не только вычислительный метод, но и формализованный конвейер преобразования данных, гарантированно приводящий к результату. Именно это и реализовано в работе:
Парсинг xlsx-таблиц во внутреннее представление;
Построение графа сети и автоматическая генерация матрицы инцидентности;
Формирование полной системы уравнений и неравенств по единым правилам для любой топологии;
Формирование нелинейной целевой функции на основе произвольных исходных данных;
Запуск оптимизации с ограничениями и начальными условиями;
Обратное преобразование результатов в инженерные матрицы и графы.
Инженер подаёт на вход две таблицы и получает на выходе готовые матрицы оптимальных маршрутов и схему загрузки линий. Ни одной формулы ему выписывать не нужно. Именно эта последовательность шагов, превращающая исходные данные в прикладной результат, и является инженерным алгоритмом.
В телекоммуникациях инженер ищет ответ на вопрос: как направить взрывной трафик в час пиковой нагрузки, не допустив деградации голосовых и видеосервисов?
Далеки всё ещё наши теоретики от реальных задач. Очень далеки.
В данной работе решается фундаментальна задача: выполняется строгий расчёт распределения потоков, гарантирующий, что ни одна линия не выйдет на гиперболический рост очереди. Что именно передавать - голос, видео, телеметрию или команды управления - это вопрос входных данных. Инженерные интерпретации могут быть разные.
Все-таки это очень теоретическая работа.
Во-первых, ну нет на практике нигде сети, где у вас сразу возникает n потоков и больше ничего, и все они существуют строго одно и то же время. Каждый поток возникает независимо от остальных, в произвольное время. У вас никогда нет задачи искать вот так n потоков. У вас есть уже как-то загруженная сеть и вы строите один маршрут для конкретного соединения. Возможно оставляя обходные пути на случай, если возникнет какой-то другой запрос.
Во-вторых, у вас тут централизованный control plane. Какой-то Software Defined Networking. Это возможно только в очень отдельных случаях. У вас какой-то свой датацентр и вы внутри что хотите то и городите. Но там практически нет задач выделить поток определенной пропускной способности. Обычно вам или надо передать данные как можно быстрее, или не так важно как передавать и тут работают приоритеты и сходимость скорости за счет какого-нибудь отката вроде как в TCP. И очереди не растут гиперболически, ибо достаточно дропать пакеты и отправитель снижает свои аппетиты сам.
Ну и пуассоновские допущения об интенсивности потоков тоже очень теоретические.
А может ваша программа решить бензиновый кризис?
Оптимизация распределения потоков в системах массового обслуживания