QIOPT: новые лучшие решения
задачи раскраски решётки
Мы применили квантово-вдохновлённый оптимизатор к классической задаче OEIS A227133 и нашли 10 новых рекордов для n = 21..30.
Суть задачи A227133
Представим квадратную решётку n × n. Нужно закрасить как можно больше клеток так, чтобы никакие четыре закрашенные клетки не образовали вершины квадрата, стороны которого параллельны осям.
Попробуйте сами
Нажмите на клетки решётки 6×6. Ваша задача — закрасить как можно больше, но не допустить квадратов.
История исследований
Задача A227133 — это открытый долгосрочный «контест», в котором разные методы соревнуются за лучшие решения.
Перебор (Exhaustive)
< 2010n = 1...9. Полный перебор всех вариантов.
MIP (G. Resta)
2013n = 10. Целочисленное программирование.
MIP (Gurobi)
2014n = 12, 13. 141 день расчётов на 32 ядрах.
Ascension (P. Karpov)
2015n = 11–16. Табу-поиск и имитация отжига.
D. Kamenetsky
2016n = 17–20. Имитация отжига. Best known до 2025.
QIOPT
2025n = 21–30. Новые рекорды с помощью QUBO.
От задачи к PUBO 4-й степени
Для QIOPT эта задача – естественный кандидат.
Мы формулируем её в виде
Polynomial Unconstrained Binary Optimization (PUBO) четвёртой степени:
целевая функция и штрафы записываются как полином от бинарных переменных.
Затем эта PUBO-модель автоматически приводится к внутреннему Ising/QUBO-представлению.
Результаты QIOPT
Мы воспроизвели известные оптимумы для n ≤ 20
и нашли новые рекордные конфигурации для n = 21..30.
Известные и новые решения A227133
Визуализация решений
Почему это важно для бизнеса?
A227133 — это стресс-тест. Те же подходы, что решают эту задачу, оптимизируют реальные процессы.
Логистика
Маршрутизация без конфликтов ресурсов и временных окон.
Производство
Календарное планирование цеха с учётом совместимости оборудования.
Планирование
Сетевое планирование строительства (PERT/CPM) с ресурсными ограничениями.
Финансы
Оптимизация портфелей: выбор активов при наличии сложных правил исключения.