Оптимизация с ограничениями , или программирование с ограничениями (CP), — это название, данное для определения возможных решений из очень большого набора кандидатов, где проблема может быть смоделирована с точки зрения произвольных ограничений. Проблемы CP возникают во многих научных и инженерных дисциплинах. (Слово «программирование» немного неправильно употребляется, подобно тому, как слово «компьютер» когда-то означало «человек, который вычисляет». Здесь «программирование» относится к составлению плана, а не к программированию на компьютерном языке.)
CP основан на осуществимости (поиске возможного решения), а не на оптимизации (поиске оптимального решения), и фокусируется на ограничениях и переменных, а не на целевой функции. Фактически, проблема CP может даже не иметь целевой функции — цель может состоять в том, чтобы сузить очень большой набор возможных решений до более управляемого подмножества путем добавления ограничений к проблеме.
Примером проблемы, которая хорошо подходит для CP, является планирование работы сотрудников . Проблема возникает, когда компаниям, которые работают непрерывно, например фабрикам, необходимо составить еженедельные графики для своих сотрудников. Вот очень упрощенный пример: компания работает три 8-часовые смены в день и каждый день распределяет трех из четырех своих сотрудников на разные смены, а четвертому дает выходной. Даже в таком маленьком случае количество возможных расписаний огромно: на каждый день их 4! = 4 * 3 * 2 * 1 = 24 возможных назначения сотрудников, поэтому количество возможных недельных графиков равно 24 7 , что превышает 4,5 миллиарда. Обычно существуют другие ограничения, которые уменьшают количество возможных решений — например, каждый сотрудник должен работать как минимум минимальное количество дней в неделю. Метод CP отслеживает, какие решения остаются осуществимыми при добавлении новых ограничений, что делает его мощным инструментом для решения крупных реальных задач планирования.
CP имеет широкое и очень активное сообщество по всему миру со специализированными научными журналами, конференциями и арсеналом различных методов решения. CP успешно применяется в планировании, составлении графиков и во многих других областях с неоднородными ограничениями.
Инструменты
Google предоставляет несколько способов решения проблем CP :
- Решатель CP-SAT : решатель программирования ограничений , использующий методы SAT (выполнимости).
- Исходный решатель CP : решатель программирования ограничений , используемый в библиотеке маршрутизации.
Если вашу проблему можно смоделировать с помощью линейной цели и линейных ограничений, то у вас проблема линейного программирования , и вам следует рассмотреть MPsolver . (Однако проблемы маршрутизации обычно лучше всего решать с помощью нашей библиотеки маршрутизации транспортных средств , даже если их можно представить с помощью линейной модели.)
Примеры
В следующем разделе описывается решатель CP-SAT, основной решатель OR-Tools для программирования в ограничениях. (SAT означает выполнимость : решатель использует методы решения задач SAT наряду с методами CP.)
Вот несколько примеров задач планирования, которые хорошо подходят для решателя CP-SAT:
Двумя классическими задачами CP являются проблема N-ферзей и криптоарифметические головоломки .