Исследователи из MIT и ETH Цюрих разработали метод машинного обучения для улучшения решения задач смешанных целочисленных линейных программ (MILP) путем динамического выбора сепаратора.

Ученые из MIT и ETH Цюрих создали метод машинного обучения для оптимизации решений задач MILP с использованием динамического выбора сепаратора.

Решение сложных задач оптимизации, начиная от глобальной маршрутизации почтовых отправлений до управления электросетью, остается постоянной проблемой. Традиционные методы, в частности, решатели смешанно-целочисленного линейного программирования (Mixed-integer linear programming, MILP), долгое время были основными инструментами для разбора сложных задач. Однако их недостаток заключается в вычислительной сложности, что часто приводит к неоптимальным решениям или длительным временам нахождения решения. Чтобы преодолеть эти ограничения, исследователи Массачусетского технологического института (MIT) и Цюрихского федерального технологического института (ETH Zurich) разработали технику машинного обучения на основе данных, которая обещает революционизировать наши подходы и решения сложных логистических задач.

В логистике, где оптимизация является ключевым моментом, стоят огромные препятствия. В то время как у Санта-Клауса есть его волшебная саня и олени, компании, такие как FedEx, борются с лабиринтом эффективной маршрутизации праздничных посылок. Решатели MILP, программное обеспечение, на котором основаны компании, используют метод разделения и покорения, чтобы разбить обширные задачи оптимизации на более простые. Однако чрезмерная сложность этих задач зачастую приводит к длительным временам нахождения решения, которые могут занимать часы или даже дни. Компании часто вынуждены останавливать решатель на середине процесса, прибегая к компромиссным решениям из-за ограничений по времени.

Исследовательская группа выявила важный промежуточный этап в решателях MILP, который существенно влияет на длительность нахождения решения. Этот этап представляет собой управление разделителями – основной аспект каждого решателя, но склонный быть забытым. Управление разделителями, отвечающее за определение оптимальной комбинации алгоритмов разделителей, представляет собой задачу с экспоненциальным количеством потенциальных решений. Признавая это, исследователи стремились оживить решатели MILP подходом, основанным на данных.

• Недавние антропические исследования говорят, что вы можете увеличить емкость запоминания LLM на 70% с помощью всего одного добавления к вашему подсказке Раскройте силу Claude 2.1 с помощью стратегического подсказывания
• Исследователи из AI2 и Университета Вашингтона раскрывают поверхностную природу выравнивания LLMs и представляют URIAL новый метод настройки без необходимости настройки.
• Исследователи из МИТ и FAIR Meta представили RCG (Representation-Conditioned Image Generation) прорывной ИИ-фреймворк в создании изображений безусловно классифицированной.

Существующие решатели MILP используют общие алгоритмы и техники для поиска решения в огромном пространстве вариантов. Однако команда MIT и ETH Zurich внедрила механизм фильтрации для оптимизации поиска разделителей. Они сократили ошеломляющее количество потенциальных комбинаций – 130 000 – до более управляемого набора вокруг 20 вариантов. Этот механизм фильтрации основан на принципе убывающих предельных полезностей, утверждающем, что наибольшая выгода исходит от небольшого набора алгоритмов.

Инновационный подход заключается в интеграции машинного обучения в рамки решателей MILP. Исследователи использовали модель машинного обучения, обученную на проблемно-специфических наборах данных, для выбора наилучшей комбинации алгоритмов из уменьшенного набора вариантов. В отличие от традиционных решателей с предопределенными конфигурациями, этот подход, основанный на данных, позволяет компаниям настраивать решатели MILP общего назначения для решения их конкретных задач, используя свои данные. Например, компании, такие как FedEx, которые регулярно решают задачи маршрутизации, могут использовать реальные данные из прошлого опыта для усовершенствования своих решений.

Модель машинного обучения работает на основе контекстуальных бандитов, формы обучения с подкреплением. Этот итеративный процесс обучения включает выбор потенциального решения, получение обратной связи об его эффективности и его усовершенствование в последующих итерациях. Результатом является значительное ускорение решателей MILP, изменяющееся от 30% до впечатляющих 70%, без ущерба для точности.

В заключение, совместная работа между MIT и ETH Zurich является значительным прорывом в области оптимизации. Благодаря сочетанию классических решателей MILP с машинным обучением, исследовательская группа открыла новые возможности для решения сложных логистических задач. Возможность ускорения процесса нахождения решения при сохранении точности придает практичность решателям MILP, делая их более применимыми к реальным ситуациям. Это исследование вносит вклад в оптимизацию и ставит начало более широкой интеграции машинного обучения в решение сложных задач реального мира.