MILP-Evo: закрытый цикл эволюции программ для автоматического дизайна MILP-решателей
Группа исследователей опубликовала в архиве препринтов arXiv работу, посвящённую автоматическому дизайну решателей для задач смешанного целочисленного линейного программирования (MILP). Предложенный метод, получивший название MILP-Evo, использует большие языковые модели (LLM) для направленной эволюции исполняемых компонентов решателя.
MILP — класс оптимизационных задач, широко применяемых в логистике, финансах, планировании и других областях. Решатели (солверы) включают в себя множество эвристик и правил, которые традиционно проектируются вручную экспертами. Альтернативные подходы на основе машинного обучения часто дают «чёрные ящики», сложные для анализа и интеграции.
MILP-Evo решает эту проблему, формулируя задачу как замкнутый цикл эволюции программ. На каждом шаге LLM генерирует или модифицирует код компонента (например, селектора отсечений или правила ветвления). Этот код загружается в решатель SCIP через интерфейс PySCIPOpt и прогоняется на наборе MILP-примеров. Результаты вычислений (время решения, число узлов дерева) служат обратной связью для LLM — программа выбирает лучших кандидатов, исправляет ошибки и поддерживает разнообразие популяции.
Выходом метода являются явные, читаемые и модифицируемые фрагменты кода, которые можно непосредственно встраивать в стандартный рабочий процесс решателя. По утверждению авторов, это облегчает анализ, адаптацию и повторное использование результатов.
Эксперименты проводились на четырёх семействах бенчмарков. В ряде случаев эволюция под управлением LLM позволила найти конкурентоспособные специализированные политики уже в нескольких итерациях. Детали и код находятся в приложении к статье.
Разработка демонстрирует, что LLM могут эффективно участвовать в автоматическом конструировании сложного программного обеспечения для оптимизации, сочетая преимущества обучения по отклику с прозрачностью результирующей логики.
