Как решаются оптимизационные задачи в масштабе. Декомпозиция и инженерия

Всем привет. Меня зовут Василий Гуров, я занимаюсь задачами оптимизации в ML Research Lab MAGNIT TECH. В этом материале разберу два промышленных кейса из крупного ритейла – планирование смен сотрудников магазинов и сглаживание нагрузки на распределительные центры.

На поверхности это разные задачи. В первой нужно построить график работы сотрудников по ролям и временным интервалам. Во втором кейсе стоит задача перераспределения логистических потоков так, чтобы снизить пики нагрузки на распределительные центры (РЦ). Но инженерная проблема у них оказалась общей. Прямая time-indexed постановка быстро раздувала модель до сотен тысяч и миллионов бинарных переменных, давала нестабильные рекомендации и плохо укладывалась в SLA.

В этой статье я покажу, как мы решали эту проблему на практике с помощью простого приёма, который должен одним из первых рассматриваться при решении таких объёмных задач. Ключевым оказалось не выбрать самый мощный солвер или алгоритм, а взглянуть на задачу с другой стороны – изменить саму единицу решения. Вместо выбора на уровне слотов, мы стали заранее генерировать валидные кандидаты смен и дальше решали задачу выбора из этих кандидатов. В планировании графиков сотрудников таким кандидатом стала допустимая смена, в сглаживании нагрузки на РЦ – допустимый перенос потока.