Комментарии 6
Эта задача же решается через min cost max flow. Не надо тут линейного целочисленного программирования. Графовые алгоритмы могут работать лучше оптимизаторов. В одной доле у вас будут клиенты, в другой call-group-ы. Из клиента в сток ребро пропусконой способностью 1. В колгруппу из истока ребро с минимальным ограниченим mg и максимальным Mg. Между клиентом и колл-гуппой ребро с пропускной способностью 1 и ценой минус вероятность отклика.
Да, у вас очень много вершин и ребер, так что нужно будет что-то очень продвинутое. Вроде какого-нибудь push-relabel. Возможно какие-то евристические методы поиска приближенного решения тут будут работать очень хорошо. Например, можно отсортировать клиентов и брать их группами. Решать задачу отдельно в каждой группе с уменьшенными ограничениями Mg. Или решать задачу итерационно - после нахождения потока в лучшей группе, добавляем следующую группу клиентов и работаем в остаточной сети.
Не надо тут линейного целочисленного программирования
Почему не надо, если оно работает и работает хорошо?)
Графовые алгоритмы могут работать лучше оптимизаторов.
Лучше с точки зрения скорости или оптимальности решения?)
Если хотите, можете реализовать эту задачу на графах и выступить на семинаре нашего комьюнити NoML. Будем рады послушать и сравнить результаты.
P.S. Графовые алгоритмы это круто, но в более общем случае, когда нужна выполнимость сложных контактно-продуктовых политик, непонятно, как это можно сделать на графах. Про более сложные постановки задачи и про то, как мы их ускоряем, мы рассказали на одном из наших семинаров.
Лучше с точки зрения скорости или оптимальности решения?)
Скорости решения.
но в более общем случае, когда нужна выполнимость сложных контактно-продуктовых политик, непонятно, как это можно сделать на графах
Возможно, но более общий случай вы не привели, а приведенная задача - решается через min cost max flow.
Скорости решения.
А что с оптимальностью будет? Скорость можно по разному повышать -- например, разбивая на подзадачи, как это и делалось изначально. Но это может приводить к субоптимальному решению.
В общем наше приглашение на семинар в силе. Если что пишите в ЛС)
> А что с оптимальностью будет?
Это точные алгоримты. Они находят глобальный минимум целевой функции.
Ни на какие семниары ходить не собираюсь. Это ваша задача. Можете попробовать запустить какой-нибудь networkX на ваших данных, посмотреть как быстро работает, если вам интересно. Есть сильно ненулевой шанс, что этот кардинально другой подход будет решать вашу задачу быстрее оптимизаторов общего назначения. Если вам это не интересно - ваше право.
На всех постах об оптимизационных задачах и алгоритмах всегда ожидаю твои комменты😀я твой фанат
Как нам удалось в 100 раз ускорить решение оптимизационной задачи NBO в Альфа-Банке