Парадигма программирования для поиска одного решения среди 8 080 104 кандидатов
Программирование с ограничениями — это способ найти каждое решение, которое соответствует набору предопределенных ограничений.
Это бесценный инструмент для специалистов по обработке и анализу данных для решения огромного количества задач, таких как планирование, составление расписаний, последовательность и т. д. В этой статье мы увидим, как использовать CP двумя разными способами:
- Выполнимость: цель состоит в том, чтобы найти одно или несколько возможных решений (то есть решений, которые учитывают наши ограничения) путем сужения большого набора потенциальных решений;
- Оптимизация: цель состоит в том, чтобы найти наилучшее возможное решение в соответствии с целевой функцией, как в линейном программировании (ЛП).
Мы будем использовать CP-SAT от Google OR-Tools, отличный бесплатный решатель CP с открытым исходным кодом. Обратите внимание, что он отличается от MPSolver, предназначенного для линейного и смешанного целочисленного программирования. Разница между CP и LP довольно запутанная, мы коснемся этой темы в конце статьи.
Вы можете запустить код со следующим блокнотом Google Colab.
🪖 I.Удовлетворительность задачи о трех скаутах
В предыдущей статье мы создали армию, чтобы победить нашего противника. Но была одна маленькая проблема: нам нужно было угадать, насколько могущественна его армия.
На этот раз давайте отправим разведчиков, чтобы узнать точное число. Наши 3 разведчика наблюдали за вражеским лагерем, и вот что они нам сообщают:
- Разведчик 1: «количество солдат кратно 13»;
- Разведчик 2: «количество солдат кратно 19»;
- Разведчик 3: «количество солдат кратно 37»;
- Все они согласны с тем, что количество солдат не превышает 10 000.
У наших разведчиков есть собственный способ подсчета солдат, но мы можем объединить эти три наблюдения, чтобы создать модель.
Назовем количество солдат армией. Мы можем перевести нашу проблему в следующую систему конгруэнтности:
Если вы не знакомы с этим обозначением, вот что оно означает в терминах программирования:
Давайте реализуем это с помощью OR-Tools. Первое, что нам нужно сделать, это импортировать и создать модель и решатель CP-SAT.
Процесс моделирования очень похож на то, что мы делали в линейном программировании.
Первым шагом для создания нашей модели CP является объявление переменных. В этом примере у нас есть только одно: армия, количество солдат.
Мы должны дать нижнюю и верхнюю границы. нижняя граница равна 1, так как мы знаем, что есть армия, а верхняя граница по данным разведчиков составляет 10 000 человек:
В OR-Tools мы используем метод NewIntVar для создания этой переменной.
Второй шаг — объявить ограничения.
В этом примере мы определили три ограничения. Modulo — это специальный оператор, поэтому нам нужна специальная функция для его обработки с помощью CP-SAT: AddModuloEquality. Вы можете найти справочник по этому адресу, если вам нужны другие методы.
В отличие от линейного программирования, здесь нам не нужно определять целевую функцию.
Причина проста: нечего оптимизировать! Мы просто хотим найти выполнимое решение, удовлетворяющее нашим ограничениям, но не существует «хороших» или «плохих» ответов. Это ключевая особенность программирования с ограничениями.
Наша модель завершена, теперь мы можем попросить OR-Tools решить ее.
================= Solution ================= Solved in 0.00 milliseconds 🪖 Army = 9139 Check solution: - Constraint 1: 9139 % 13 = 0 - Constraint 2: 9139 % 19 = 0 - Constraint 3: 9139 % 37 = 0
Мы получили решение менее чем за миллисекунду: во вражеской армии 9 139 солдат. Ура, теперь мы можем уволить разведчиков!
Мы ограничили область поиска верхней границей в 10 000, что дало нам уникальное решение. Но так ли это, если мы раздвинем этот предел?
Еще одним преимуществом CP является способность находить все возможные решения проблемы. Это может занять много времени, когда пространство поиска велико, потому что решатель должен переборщить все пространство (вместо того, чтобы уменьшать его с помощью эвристики). Давайте изучим эту функцию, распечатав каждое возможное решение с новой верхней границей 100 000.
С помощью OR-Tools мы просим решатель искать все возможные решения благодаря параметру enumerate_all_solutions. Затем мы назначаем ему класс обратного вызова, который печатает каждое решение, найденное решателем.
Мы нашли 10 решений! Этого и следовало ожидать, поскольку мы увеличили верхнюю границу в десять раз: все эти решения кратны числу 9139.
Как видите, этот пример не имеет ничего общего с оптимизацией: это чистая проблема выполнимости. С другой стороны, эту систему конгруэнтности можно решить вручную с помощью китайской теоремы об остатках. Но КП этим не ограничивается…
🍻 II. Оптимизация и пиво
Давайте посмотрим на другую проблему: наша армия встретится с врагом через несколько дней. Тем временем интендант должен приготовить пайки, которые будут использоваться во время похода.
Место в фургонах с припасами ограничено, и некоторые пайки более популярны, чем другие. Возможны три рациона:
- 🥖 Хлеб: занимает всего 1 место, но солдатам он не очень нравится при популярности 3;
- 🥩 Мясо: занимает 3 места и имеет популярность 10;
- 🍺 Пиво: занимает 7 мест, но солдаты любят его с популярностью 26.
Вагоны снабжения вмещают 19 мест. Как выбрать лучшие рационы, чтобы максимизировать популярность?
Это проблема оптимизации, которую мы уже видели: на самом деле это вариант знаменитой задачи о рюкзаке. Мы могли бы повторно использовать код из предыдущей статьи и просто изменить входные параметры.
На этот раз мы решим ее с помощью программирования с ограничениями. Эта парадигма не ограничивается поиском возможных решений. Он также может выполнять оптимизацию с использованием других алгоритмов для обработки этих накладных расходов.
Создадим модель проблемы. Прежде всего, мы должны объявить три переменные: 🥖хлеб, 🥩мясо и 🍺пиво. Их может быть 0, но их количество не может превышать максимальную вместимость.
На этот раз у нас есть только одно ограничение: место, занимаемое хлебом, мясом и пивом, не может превышать вместимость вагонов (19).
Мы хотим максимизировать общую популярность выбранных рационов:
Модель завершена, CP-SAT может решить проблему!
================= Solution ================= Solved in 0.00 milliseconds Optimal value = 68 popularity Food: - 🥖Bread = 2 - 🥩Meat = 1 - 🍺Beer = 2
Мы получили самую высокую популярность (68) из возможных при вместимости 19.
Соблюдается ли ограничение? Давайте быстро проверим: 1×2 🥖 + 3×1 🥩 + 7×2 🍺 = 19, что действительно ≤ 19.
Хорошо, я хотел бы задать еще один вопрос: сколько существует решений этой проблемы? Еще раз, мы можем ответить на это специальным обратным вызовом, чтобы подсчитать их.
121
Мы нашли 121 решение с пропускной способностью 19. Но это число быстро увеличивается: при емкости 1000 существует 8 080 104 возможных решения! И все же CP-SAT находит оптимальное решение менее чем за секунду. Как это возможно?
Решатели CP не перебирают проблему методом полного перебора, а вместо этого сочетают эвристику и комбинаторный поиск. В частности, тремя наиболее популярными методами решения проблем удовлетворения ограничений являются возврат, распространение ограничений и локальный поиск.
CP-SAT весьма специфичен, поскольку сочетает в себе CP и SAT: он является частью более широкой тенденции слияния CP, LP, SAT и метаэвристики.
Мы сказали, что предыдущую задачу можно решить с помощью линейного программирования, поэтому давайте сравним код обоих решений:
Как видите, синтаксис очень похож, но это не одно и то же: модель/решатель против решателя, NewIntVar вместо IntVar и т. д. Нужно немного перевести, но с этим легко справиться.
Эти два метода невероятно близки друг другу: они оба обрабатывают переменные с ограничениями и выполняют оптимизацию с использованием математики и эвристики. Однако CP ограничивается дискретными параметрами, а LP — непрерывными. С другой стороны, вы можете реализовать специализированные ограничения типа все разные в CP, но не в LP. Вот краткое изложение основных различий между этими двумя технологиями:
Если вы хотите узнать больше об этой теме, я бы порекомендовал эту статью Ирвина Дж. Люстига и Жана-Франсуа Пюже. В документации CPLEX также подробно описаны различия по этому адресу с точки зрения моделирования и оптимизации.
Заключение
Программирование с ограничениями — еще одна невероятная техника в наборе инструментов математической оптимизации. Это радикально отличается от традиционного декларативного программирования. В этой статье,
- Мы видели два применения CP с выполнимостью и оптимизацией;
- Мы реализовали модели CP в OR-Tools и поэкспериментировали с функцией обратного вызова;
- Мы выделили различия между CP и LP.
В этом введении мы ограничились простыми задачами, но CP имеет удивительные применения в сложных задачах планирования и маршрутизации. Это тема, которую я хотел бы затронуть в следующей статье.
Если вам интересно узнать об этом больше, не стесняйтесь подписываться на меня в Twitter по адресу @maximelabonne. Спасибо за внимание!
