В данной статье мы, Advanced Analytics GlowByte, расскажем, как нам удалось ускорить решение задачи NBO на open-source солвере CBC примерно в 100 раз и добиться повышения оптимального значения целевой функции на 0,5%.
Введение
Задача NBO в нашем случае – это составление оптимального плана коммуникаций с клиентской базой на ближайшую неделю в различных каналах (звонок, смс и т. д.). Более подробно о постановке такой задачи и ее решении мы рассказывали в статье и на семинаре в нашем комьюнити NoML.
Напомним кратко смысл задачи и ее математическую постановку. У нас есть база данных из 
клиентов банка. Мы хотим предлагать им определенные продукты: кредит, депозит и т. д. Для этого мы можем контактировать с ними по определенным каналам: можем позвонить, отправить СМС и т. д. Допустим, для каждого клиента мы оценили вероятность отклика этого клиента на предложение данного продукта по данному каналу. Под откликом имеем в виду открытие продукта клиентом в течение некоторого времени после того, как мы предложим этот продукт клиенту. Мы хотим составить план коммуникаций на неделю, т. е. ответить на вопрос, каким клиентам какие продукты по каким каналам предлагать, чтобы максимизировать ожидаемое число откликов и чтобы соблюсти ряд бизнес-требований:
-
с клиентом можно коммуницировать не более одного раза;
-
у клиентов могут быть запрещенные продукты или каналы, по которым коммуницировать нельзя;
-
есть ограничения на суммарное число коммуникаций по парам "продукт-канал".
Эту задачу можно сформулировать в виде целочисленной задачи линейного
программирования:
— индекс клиента.
— индекс пары продукт-канал. Далее пару продукт-канал будем называть коллгруппа (callgroup).
— переменные задачи. Они бинарные, если 
то с клиентом 
нужно проконтактировать по коллгруппе 
Если 
то ненужно.
— вероятность отклика клиента 
на коммуникацию по каналу, соответствующему коллгруппе 
— множество индексов коллгрупп 
по которым можно коммуницировать с клиентом 
— мин. и макс. допустимый объем коммуникаций (капасити) для коллгруппы 
Далее, используя любой солвер для решения такого рода задач, мы получим оптимальный план коммуникаций, удовлетворяющий нашим требованиям. В нашем случае используется солвер CBC.
Сложности и их текущие решения
Число клиентов, для которых мы хотим составлять планы коммуникаций, — десятки миллионов. Число переменных и ограничений в задаче оптимизации — сотни миллионов. При таком размере эта задача решается полтора дня, что слишком долго. У нас есть требование на время решения задачи — примерно 20 минут.
Чтобы решить эту проблему, делалось следующее приближение. Вся клиентская база разбивалась на маленькие группы — чанки (chunks). Для каждого чанка ставилась такая же задача оптимизации, как описано в предыдущем разделе, только 
и 
делились на число чанков. Далее задачи решались по отдельности.
— число чанков.
— мин. и макс. капасити для коллгруппы 
для одного чанка. 
- мин. и макс. капасити для коллгруппы 
для всей клиентской базы.
Множество "маленьких" задач решаются быстрее, чем одна большая, так как время решения задачи увеличивается нелинейно с ростом числа переменных. К тому же, разбивая большую задачу на множество меньших, мы можем распараллелить процесс и значительно ускорить вычисления. Однако такое ускорение имеет свою цену: существует риск получить неоптимальный план коммуникаций. Разбиение задачи накладывает отдельные ограничения на количество коммуникаций внутри каждой подзадачи, которые могут быть жестче, чем в исходной задаче. Это приводит к тому, что часть допустимых решений, включая оптимальные, может быть упущена. В результате итоговый план коммуникаций, составленный на основе решений подзадач, может оказаться субоптимальным.
Цель нашего эксперимента — увеличить размер чанков (подзадач), тем самым уменьшив их количество, и оценить, как это отразится на росте целевой функции. Важно, чтобы при этом время решения не увеличилось. Основной вызов заключается в оптимизации времени решения. Поэтому, прежде чем увеличивать размер чанков, мы должны ускорить процесс решения задач.
Правим настройки CBC
Изменение настроек дало значительный прирост скорости на нашей задаче. Ниже перечислены настройки, которые мы переопределили, и объяснения, зачем это было сделано.
preprocess=off. Эта настройка отключает преобразования задачи, связанные с условиями целочисленности. Эти преобразования опциональные, их смысл — ускорить решение задачи. В нашей задаче от этих преобразований мало пользы, и на них уходит много времени. В итоге отключить препроцессинг оказывается более выгодно.
heur=off, rens=on. Эта пара настроек говорит CBC использовать только одну эвристику — RENS. В нашей задаче релаксация сразу находит целочисленное решение. Но CBC все равно тратит время на вызов эвристик. Поэтому мы оставляем только одну, которая отрабатывает быстро. В принципе можно было отключить эвристики вообще, но разницы во времени это не дает. Мы оставили одну эвристику на всякий случай.
zero=off. Эта настройка отключает один из методов отсечений. В нашей задаче это не нужно, потому что и без них мы находим хорошее решение. Но на этот метод уходит заметное время.
presolve=off. Эта настройка отключает общие преобразования задачи (не обязательно связанные с целочисленностью). Их смысл в том, чтобы эквивалентными преобразованиями упростить постановку задачи. Например уменьшить число переменных или ограничений. Трудно наверняка предсказать, как это повлияет на дальнейший ход решения, но обычно уменьшение размера задачи ускоряет решение. Однако в нашей задаче пресолв не помогает. Без него задача решается заметно быстрее.
slog=0. Эта отключает некоторые логи, которые нам не интересны. Мы это делаем, чтобы не засорять логи в Airflow. На перформанс это не влияет.
Переопределяем вызов CBC из Pyomo
Pyomo — это питоновская библиотека для постановки оптимизационных задач. В этом разделе описаны некоторые шаги, которые пришлось сделать, чтобы обойти пару проблем с CBC и Pyomo. Это дало в итоге значительный прирост скорости.
Pyomo всегда вызывает CBC с настройкой -stat=1, которая говорит ему собрать статистику о задаче и написать это в лог. Нам это не нужно, т. к. на ход решения это никак не влияет. В нашем случае на сбор этой статистики времени уходит значительно больше, чем на само решение. В интерфейсе Pyomo возможности не передавать эту настройку нет. Мы зарепортили это в github репе Pyomo. Авторы согласились взять это в работу, но неизвестно, когда это будет сделано. А пока мы сделали костыль, чтобы не передавать эту настройку в CBC.
Обычно для решения задачи в CBC используется его команда solve. Когда Pyomo вызывает CBC, он использует именно ее. Мы заметили, что настройка presolve=off не имеет эффекта, если вызвать эту команду. Но если вместо solve использовать две последовательные CBC команды — initialSolve, branch, то настройка имеет эффект. По смыслу эти две команды делают то же самое, что и одна команда solve. Видимо, в CBC есть проблема с тем, чтобы применить эту настройку из команды solve. Для того, чтобы применить presolve=off настройку, мы сделали костыль, чтобы Pyomo при вызове CBC использовал пару команд initialSolve, branch вместо solve.
Вводим вспомогательные переменные в задачу
Существенное ускорение при увеличении размера чанков дал следующий подход. Введем новые переменные как суммы исходных переменных 
с одинаковыми коэффициентами целевой функции и одинаковой коллгруппой. И перепишем через эти переменные целевую функцию и ограничения на капасити. Составим множество уникальных коэффициентов целевой функции в задаче и пронумеруем их индексом 
— индекс уникального коеффициента целевой функции.
— уникальные значения коэффициентов 
Остальные обозначения такие же, как в исходной задаче.
Результаты
Мы сравнили время решения задачи до и после изменений. Пробовали разные размеры чанков и замеряли относительный прирост скорости. Результат показан на графике ниже.
Как видно, чем больше размер задачи, тем больше прирост скорости. Мы достигли ускорения до 80 раз.
Теперь, когда нам удалось значительно ускорить процесс, мы можем решать более крупные подзадачи за то же время. Это позволяет увеличить размер чанков (уменьшить количество подзадач), на которые разбивается исходная задача. Вопрос заключается в том, насколько имеет смысл увеличивать размер. Чтобы ответить на этот вопрос, мы провели измерения прироста целевой функции при увеличении размера чанков (Рис. 2).
Прирост измерялся относительно разбиения на 150 подзадач (точка с "размер чанков=1"), поэтому для этой точки прирост равен нулю. Максимальный прирост составил около 0,5%. Увеличение размера чанков более чем в 30 раз не дает значительного прироста. Однако время решения значительно увеличивается с ростом размера чанков. Поэтому мы остановились на увеличении размера чанков в 30 раз, что соответствует сокращению их числа со 150 до 5.
Над статьей работали @Lazarev_Adrian@anikonorov@vagonoff
P. S. Про то, как мы ускоряем оптимизационные open-source солверы, мы рассказывали на одном из семинаров нашего сообщества NoML.
Автор: vagonoff
