Engee

Проблемно-ориентированная оптимизация 🔢 (Часть 1. Судоку)

2024-11-01 09:17 ПОСТ
Друзья,

Наступил ноябрь. С деревьев опадают последние листья, и с каждым днем становится все холоднее. А это означает, что сейчас самое время оптимизировать все процессы перед наступлением зимы! ☃️
Проблемно-ориентированная оптимизация — это подход к решению задач оптимизации, который фокусируется на адаптации методов к конкретным характеристикам и требованиям каждой задачи.
В первом примере мы погрузимся в увлекательный мир решения судоку в Engee. Продемонстрируем два подхода к решению этой классической головоломки: смешанное целочисленное линейное программирование (MILP) и программирование в ограничениях (CP).
Итак, мы создали свой собственный генератор головоломок с варьируемым уровнем сложности и описали функции для визуализации судоку.
Затем находим решение головоломки с помощью метода MILP. Для этого:
  • сформулируем задачу оптимизации и создадим бинарные переменные с помощью библиотеки JuMP;
  • самостоятельно сформулируем и применим ограничения для строк, столбцов и 3x3 подсеток;
  • решим сформулированную задачу с помощью решателя HiGHS, зафиксируем заданные числа и визуализируем решение;
А с решением головоломки с помощью метода CP мы рекомендуем вам ознакомиться самостоятельно в Сообществе!
Кстати, подобные подходы могут быть использованы и в более серьезных задачах, например, в планировании и распределении ресурсов или оптимизации производственных процессов.
Желаем вам увлекательного погружения в мир оптимизации и ждем вас в Engee!