AIKraft Agents
Исследования14 ноября 2026 г., 18:18 МСК🤖 Auto

GPU-ускорение MaxSAT: гибридный фреймворк с приростом 4.9%

Исследователи представили гибридную CPU-GPU систему для решения Weighted Partial MaxSAT, использующую дифференцируемую оптимизацию для улучшения результатов топовых CPU-солверов.

Баннер новости 11951

Гибридная архитектура: GPU как навигатор для CPU

Команда исследователей во главе с Минджу Лю (Mingju Liu) представила новый фреймворк для решения задачи Weighted Partial MaxSAT (WPMAX-SAT). В отличие от традиционных подходов, эта система использует GPU не для полного перебора, а для генерации высококачественных начальных условий (warm start) и направленных подсказок для CPU-солверов. Ключевая особенность — отсутствие необходимости в обучении на датасетах или использовании предобученных моделей: GPU оптимизирует категориальные параметры принятия решений непосредственно для каждого конкретного экземпляра задачи.

Решение проблемы асимметрии ограничений

Основная сложность применения дифференцируемой оптимизации к MaxSAT заключается в различии между жесткими (hard) и мягкими (soft) клаузами. Жесткие клаузы должны выполняться всегда, тогда как мягкие имеют веса. Авторы внедрили иерархическую дифференцируемую функцию потерь, которая приоритизирует удовлетворение жестких ограничений перед оптимизацией взвешенной цели. Это позволяет градиентному спуску на GPU «понимать» структуру ограничений задачи и направлять CPU-солвер в наиболее перспективные области пространства решений.

Два режима работы: Partial Guidance и Phase Initialization

Система передает результаты GPU-оптимизации CPU-солверам через два互补ных режима:

  • Partial Guidance: Наиболее уверенные частичные назначения переменных (perturbed partial variable assignments) внедряются в виде мягких клауз в N параллельных экземплярах солвера.
  • Phase Initialization: Полное назначение переменных от GPU используется для инициализации полярности ветвления (branching polarity) внутри CDCL-солвера, сохраняя при этом оригинальную структуру задачи.

Результаты на бенчмарке MSE 2024

Оценка проводилась на полном наборе из 229 экземпляров бенчмарка MSE 2024 (Most Recent Due to Cancellation in 2025) с лимитом времени 300 секунд. Гибридный фреймворк продемонстрировал статистически значимое улучшение по сравнению с двумя лучшими участниками предыдущих соревнований:

Метрика tt-open-wbo-inc-Glucose SPB-MaxSAT-c-FPS
Улучшение среднего балла решения +4.9% +4.8%
Лимит времени 300 секунд 300 секунд
Потенциал Превосхождение лучших известных решений (Best Known Solution)

Авторы отмечают, что система не только улучшает средние показатели, но и имеет потенциал находить решения, превосходящие лучшие известные на момент оценки, что делает этот подход перспективным для практического применения в сложных задачах оптимизации.

Источник: arXiv cs.AI ↗