В то время как у Санта-Клауса могут быть волшебные сани и девять отважных оленей, которые помогут ему доставлять подарки, для таких компаний, как FedEx, проблема оптимизации эффективной маршрутизации праздничных посылок настолько сложна, что они часто используют специальное программное обеспечение для поиска решения.
Это программное обеспечение, называемое решателем линейного программирования смешанных целых чисел (MILP), разбивает огромную задачу оптимизации на более мелкие части и использует общие алгоритмы, чтобы попытаться найти лучшее решение. Однако решателю могут потребоваться часы или даже дни, чтобы прийти к решению.
Этот процесс настолько обременителен, что компании часто приходится останавливать разработку программного обеспечения на полпути, принимая решение, которое не является идеальным, но является лучшим, которое можно создать за определенный промежуток времени.
Исследователи из MIT и ETH Zurich использовали машинное обучение для ускорения процесса.
Они определили ключевой промежуточный этап в решателях MILP, который имеет так много потенциальных решений, что на его раскрытие уходит огромное количество времени, что замедляет весь процесс. Чтобы упростить этот шаг, исследователи применили технику фильтрации, а затем использовали машинное обучение, чтобы найти оптимальное решение для конкретного типа проблем.
Их подход, основанный на данных, позволяет компании использовать собственные данные для адаптации универсального решателя MILP к поставленной задаче.
Этот новый метод ускорил работу решателей MILP на 30–70 процентов без какого-либо снижения точности. Можно использовать этот метод для более быстрого получения оптимального решения или, для особенно сложных задач, лучшего решения за приемлемый промежуток времени.
Этот подход может использоваться везде, где используются решатели MILP, например, службами такси, операторами электросетей, дистрибьюторами вакцин или любой организацией, сталкивающейся с сложной проблемой распределения ресурсов.
«Иногда в такой области, как оптимизация, люди часто думают о решениях либо как о чисто машинном обучении, либо как о чисто классических решениях. Я твердо верю, что мы хотим получить лучшее из обоих миров, и это действительно яркое воплощение этого гибридного подхода», — говорит старший автор Кэти Ву, доцент Гилберта У. Уинслоу по развитию карьеры в области гражданского и экологического строительства ( CEE), а также член Лаборатории систем информации и принятия решений (LIDS) и Института данных, систем и общества (IDSS).
Ву написал статью совместно с ведущими авторами Сириу Ли, аспиранткой IDSS, и Вэньбинь Оуян, аспиранткой из Центральной и Восточной Европы; а также Макс Паулюс, аспирант ETH Zurich. Исследование будет представлено на конференции по нейронным системам обработки информации.
Трудно решить
Проблемы MILP имеют экспоненциальное количество потенциальных решений. Например, скажем, коммивояжер хочет найти кратчайший путь, чтобы посетить несколько городов, а затем вернуться в город своего происхождения. Если существует много городов, которые можно посетить в любом порядке, количество потенциальных решений может превысить количество атомов во Вселенной.
«Эти проблемы называются NP-сложными, а это означает, что маловероятно, что существует эффективный алгоритм для их решения. Когда проблема достаточно велика, мы можем только надеяться на неоптимальную производительность», — объясняет Ву.
Решатель MILP использует множество методов и практических приемов, которые позволяют достичь разумных решений за приемлемый промежуток времени.
Типичный решатель использует подход «разделяй и властвуй», сначала разбивая пространство потенциальных решений на более мелкие части с помощью метода, называемого ветвлением. Затем решатель использует технику, называемую обрезкой, чтобы сжать эти более мелкие части, чтобы их можно было искать быстрее.
При резке используется набор правил, которые сужают пространство поиска, не удаляя при этом каких-либо возможных решений. Эти правила генерируются несколькими десятками алгоритмов, известных как сепараторы, которые были созданы для различных типов задач MILP.
Ву и ее команда обнаружили, что процесс определения идеальной комбинации алгоритмов сепаратора сам по себе является проблемой с экспоненциальным числом решений.
«Управление сепараторами является основной частью любого решателя, но это недооцененный аспект проблемного пространства. Одним из результатов этой работы является определение проблемы управления сепараторами как задачи машинного обучения», — говорит она.
Сокращение пространства решений
Она и ее коллеги разработали механизм фильтрации, который сокращает пространство поиска разделителей с более чем 130 000 потенциальных комбинаций до примерно 20 вариантов. Этот механизм фильтрации основан на принципе уменьшения предельной отдачи, который гласит, что наибольшую выгоду принесет небольшой набор алгоритмов, а добавление дополнительных алгоритмов не принесет особых улучшений.
Затем они используют модель машинного обучения, чтобы выбрать лучшую комбинацию алгоритмов из 20 оставшихся вариантов.
Эта модель обучается на наборе данных, специфичном для задачи оптимизации пользователя, поэтому она учится выбирать алгоритмы, которые лучше всего подходят для конкретной задачи пользователя. Поскольку такая компания, как FedEx, уже много раз решала проблемы с маршрутизацией, использование реальных данных, почерпнутых из прошлого опыта, должно привести к лучшим решениям, чем каждый раз начинать с нуля.
Итеративный процесс обучения модели, известный как контекстные бандиты, форма обучения с подкреплением, включает в себя выбор потенциального решения, получение отзывов о том, насколько оно хорошее, а затем повторную попытку найти лучшее решение.
Этот подход, основанный на данных, ускорил работу решателей MILP на 30–70 процентов без какого-либо снижения точности. Более того, ускорение было одинаковым, когда они применили его к более простому решателю с открытым исходным кодом и к более мощному коммерческому решателю.
В будущем Ву и ее коллеги хотят применить этот подход к еще более сложным задачам MILP, где сбор размеченных данных для обучения модели может оказаться особенно сложной задачей. Возможно, они смогут обучить модель на меньшем наборе данных, а затем настроить ее для решения гораздо более серьезной задачи оптимизации, говорит она. Исследователи также заинтересованы в интерпретации изученной модели, чтобы лучше понять эффективность различных алгоритмов сепаратора.
Это исследование частично поддерживается Mathworks, Национальным научным фондом (NSF), Amazon Science Hub MIT и Комитетом поддержки исследований MIT.