Суть HyCO
HyCO — Hybrid Neural Solver for Combinatorial Optimization. Метод строит префикс решения с помощью RL-решателя. Затем адаптивно переключается на условную диффузионную модель. Она достраивает оставшиеся решения. Гибрид решает задачи нейронной комбинаторной оптимизации. Его задача — соединить сильные стороны двух классов решателей.
Работа доступна как arXiv:2609.07990. Авторы: Yuheng Li, Di Yang, Haipeng Chen, Yanhai Xiong. Препринт относится к cs.LG и cs.AI. Авторы подали версию v1 7 Sep 2026. Эти данные помогают найти первоисточник и проверить детали.
Практический смысл: HyCO не заменяет один решатель другим, а управляет переходом между ними.
Где ломаются одиночные стратегии
Sequential RL-решатели и глобальные DM-решатели показывают взаимодополняющие режимы отказа. Это видно в оптимизационном regret.
| Класс решателя | Сильная сторона | Слабое место |
|---|---|---|
| Sequential RL | Малый маргинальный regret на ранней стадии построения | Ошибки накапливаются по горизонту; regret растёт сверхлинейно |
| Global DM | Избегает накопления по горизонту | Линейный или сублинейный regret относительно размерности оставшегося нерешённого подпространства |
Вывод: провалы не совпадают. RL хорош в начале, но страдает от горизонта. DM не копит горизонтную ошибку, но платит за размер оставшейся задачи. Гибридизация использует этот разрыв.
Теоретическая рамка переключения
Авторы строят единую теоретическую рамку масштабирования ошибок. При явных предположениях о масштабировании ошибок рамка доказывает два положения.
- Гибридная структура даёт строго меньший ожидаемый regret, чем каждая из двух базовых схем по отдельности.
- Существует единственный оптимальный шаг переключения, который минимизирует regret гибрида.
Авторы определяют оптимальный шаг на уровне ожидаемого regret. На отдельных траекториях его нельзя вычислить напрямую. Поэтому нужен практический триггер.
Вывод: теория отвечает, почему гибрид помогает и когда запускать передачу. Она не даёт готовой формулы для каждой траектории.
Как работает адаптивный триггер
HyCO использует лёгкий адаптивный триггер. Триггер объединяет энтропию политики и расхождение RL-DM. Эти сигналы выявляют смену режима на уровне траектории. Они служат практическим прокси. Такой прокси нужен, потому что оптимальный шаг переключения не вычисляется на отдельной траектории.
Триггер завершает префикс RL. Условная DM достраивает оставшиеся решения. Практический критерий: следить за энтропией политики и расхождением RL-DM. Эти сигналы указывают на смену режима и момент передачи. Триггер остаётся лёгким и адаптивным.
Эксперименты и критерий выбора
В экспериментах на разнообразных бенчмарках HyCO даёт устойчивые улучшения относительно обоих базовых решателей. Результаты также подтверждают эмпирическую эффективность адаптивного триггера.
Практический критерий выбора: нужен inference-алгоритм для комбинаторной оптимизации. Он использует RL для раннего префикса и DM для оставшихся решений. Гибрид снижает ожидаемый regret относительно каждой базовой схемы. HyCO подходит как слой переключения поверх RL-поиска и диффузионной достройки. Он управляет переходом между ними.
