Программирование в ограничениях
- Автор метода
- Rossi, van Beek & Walsh
- Год
- 2006
- Тип
- Declarative combinatorial optimization
- Семейство
- Mathematical programming
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Программирование в ограничениях (CP) — это декларативная парадигма оптимизации, в которой задача формулируется как набор переменных, конечных доменов и ограничений, а решатель систематически ищет присваивания, удовлетворяющие всем ограничениям.
CP, всесторонне формализованное Росси, ван Биком и Уолшем в их Handbook of Constraint Programming (2006), объединяет отсечение на основе распространения с интеллектуальным поиском с возвратом для решения комбинаторных задач в областях составления расписаний, планирования и конфигурирования.
Интуиция метода
Представьте CP как решение сложной головоломки: каждая ячейка — это переменная с набором допустимых значений, а каждое правило головоломки — это ограничение. Вместо слепого угадывания CP использует правила для немедленного исключения невозможных значений из соседних ячеек при заполнении одной ячейки. Это распространение резко сокращает пространство поиска, поэтому решатель исследует только правдоподобные комбинации, возвращаясь и корректируя только тогда, когда достигает тупика.
История
Программирование в ограничениях возникло из исследований в области искусственного интеллекта в 1970-х годах с ранними работами по удовлетворению ограничений Монтанари и Макворта. Оно развивалось в 1980-х и 1990-х годах с разработкой алгоритмов дуговой согласованности, глобальных ограничений и практических решателей, таких как CHIP и ILOG Solver. Область была авторитетно консолидирована Росси, ван Биком и Уолшем в Handbook of Constraint Programming (2006), который остается авторитетным справочником, охватывающим теорию, алгоритмы и приложения в области комбинаторной оптимизации.
Когда применять
Программирование в ограничениях лучше всего подходит для комбинаторных задач со сложными, разнородными ограничениями — составление расписаний, составление учебных планов, конфигурирование и маршрутизация — где допустимость так же важна, как и оптимальность. Оно предполагает, что задачи могут быть смоделированы с дискретными или перечислимыми доменами переменных. CP менее эффективно для непрерывной оптимизации или крупномасштабных линейных программ, где обычно доминируют решатели линейного программирования или смешанного целочисленного программирования. Когда ограничения имеют высокоструктурированную природу и распространение может отсечь большие части пространства поиска, CP превосходит общие метаэвристики.
Ограничения и замечания
- Масштабируемость: экспоненциальный поиск в худшем случае делает CP медленным на очень больших экземплярах со слабым распространением.
- Требуется хорошее моделирование: плохие эвристики упорядочивания переменных/значений или отсутствие глобальных ограничений приводят к неоправданно большим деревьям поиска.
- Непрерывные домены: CP изначально разработано для дискретных доменов; непрерывные задачи требуют специализированных расширений или гибридных подходов.
- Экспертиза решателя: эффективное использование требует знакомства с методами моделирования ограничений и библиотеками глобальных ограничений, специфичных для решателя.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Декларативное моделирование: сложные правила реального мира выражаются непосредственно как ограничения без указания процедуры поиска.
- Мощное отсечение: распространение ограничений рано исключает недопустимые области, часто сокращая поиск на порядки.
- Обработка разнородных ограничений: логические, арифметические, глобальные и пользовательские ограничения естественно сосуществуют в одной модели.
- Гарантия полноты: решатель либо находит оптимальное решение, либо доказывает недопустимость, в отличие от эвристических методов.
Применение
- Составление расписаний сотрудников и медсестёр: назначение персонала на смены с учётом доступности, трудового законодательства и ограничений по квалификации.
- Составление учебных планов: создание университетских или школьных расписаний с учётом вместимости аудиторий, доступности преподавателей и учебных ограничений.
- Конфигурирование: сборка конфигураций продуктов (компьютеры, автомобили) из каталогов компонентов с учётом ограничений совместимости и ресурсов.
- Маршрутизация транспортных средств и логистика: планирование маршрутов доставки с учётом временных окон, грузоподъёмности транспортных средств и правил для водителей.
- Комбинаторные аукционы и распределение ресурсов: распределение ресурсов между участниками торгов или задачами с учётом ограничений эксклюзивности и бюджета.
Как это работает
Как это работает
Задача кодируется как тройка задачи удовлетворения ограничений (Constraint Satisfaction Problem), состоящая из переменных X, их конечных доменов D и набора ограничений C. Каждой переменной x_i может быть присвоено любое значение из её домена D_i. Ограничения определяют допустимые комбинации значений для подмножеств переменных, переводя правила реального мира — пределы мощности, отношения предшествования, конфликты ресурсов — в математическую структуру, с которой может работать решатель.
Формула
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}До и во время поиска решатель применяет алгоритмы дуговой согласованности (arc consistency) и другие алгоритмы локальной согласованности для отсечения значений домена, которые не могут участвовать ни в одном допустимом решении. Для каждой пары связанных переменных дуговая согласованность удаляет значения из домена одной переменной, для которых не существует поддерживающего значения в домене другой. Это распространение повторяется после каждого присваивания, значительно сокращая эффективное пространство поиска.
Формула
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}Решатель выбирает неназначенную переменную — обычно с использованием эвристик, таких как минимальное оставшееся значение (minimum remaining values) или степень (degree) — и пытается присвоить ей значение из её отсечённого домена. Распространение выполняется снова; если обнаружено противоречие (пустой домен), решатель возвращается к последней точке выбора и пробует альтернативное значение. Возврат с пропуском (backjumping) и запись неверных комбинаций (nogood recording) могут дополнительно ускорить восстановление после сбоев.
Формула
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}Когда всем переменным присвоены значения, согласующиеся с каждым ограничением, полное присваивание S* составляет решение. Для задач оптимизации целевая функция направляет поиск к наилучшему допустимому решению, а стратегии ветвей и границ (branch-and-bound) постепенно сужают границу по мере нахождения лучших решений, пока не будет сертифицирован глобальный оптимум или не будет достигнут лимит времени.
Формула
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}Частые ошибки
- Чрезмерное ограничение модели избыточными или противоречивыми ограничениями приводит к тому, что решатель некорректно сообщает о недопустимости.
- Пренебрежение глобальными ограничениями (например, alldifferent, cumulative) упускает возможности распространения, которые специализированные алгоритмы предоставляют бесплатно.
- Игнорирование эвристик поиска и полагание на стандартное упорядочивание переменных/значений может привести к пустой трате экспоненциального времени на патологические порядки.
- Смешение удовлетворения ограничений с оптимизацией: забыв добавить целевую функцию и сужение границ, получают только первое допустимое решение, а не лучшее.
Часто задаваемые вопросы
Чем программирование в ограничениях отличается от целочисленного линейного программирования?
Хотя оба метода решают комбинаторные задачи, целочисленное линейное программирование (ILP) требует, чтобы все ограничения и цели были линейными, что позволяет использовать эффективные границы релаксации линейного программирования. CP не накладывает таких требований к линейности и вместо этого полагается на распространение ограничений и систематический поиск. CP более естественно обрабатывает сложные логические и глобальные ограничения, тогда как ILP часто лучше масштабируется на задачах с сильной линейной структурой и большим количеством переменных.
Что такое глобальные ограничения и почему они важны?
Глобальные ограничения — это ограничения высокого уровня для произвольного числа переменных, например, alldifferent (все переменные принимают различные значения) или cumulative (использование ресурса в любое время не превышает его мощность). Они важны, потому что решатели реализуют для каждого из них специализированные, высокоэффективные алгоритмы распространения, достигающие гораздо более сильного отсечения, чем разложение того же условия на множество бинарных ограничений, что оставило бы большую часть пространства поиска неисследованной.
Могут ли решатели программирования в ограничениях находить оптимальные решения или только допустимые?
CP может находить оптимальные решения, комбинируя поиск допустимости с целевой функцией. Решатель использует метод ветвей и границ: после нахождения допустимого решения он добавляет ограничение, требующее, чтобы любое последующее решение было строго лучше, и продолжает до тех пор, пока не будет сертифицирована оптимальность. Если время выполнения ограничено, возвращается наилучшее найденное на данный момент решение в качестве приближения.
Похожие методы
Источники
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
ISBN: 978-0-444-52726-4Скопировано.