10.2.4. Программирование в ограничениях

Программирование в ограничениях (constraint programming) ‑ программ­ная технология для декларативного описания и эффективного решения боль­ших комбинаторных задач в областях планирования и календарного планиро­вания.

Цель программирования в ограничениях состоит в разработке языков программирования для задания ограничений и процедур поиска задач УО.

Процедура поиска в УО неявно описывает обход дерево поиска. При этом она не описывает, как обходить это дерево, это уже ‑ задача стратегий поиска. Обычно дерево поиска обходится с помощью поиска в глубину (depth-first search).

Благодаря успешному решению многих прикладных задач, стратегии поиска стали неотъ­емлемой частью языков программирования в ограничениях.

В частности, программная система OZ впервые ввела спецификацию общих стратегий поиска, которые могут быть заданы независимо от проце­дуры поиска.

Поисковый язык SALSA (Laburthe & Caseau, 1998)¹⁹ также содержит ряд заданных общих стратегий поиска.

Основные идеи, лежащие в основе программирования в ограничениях, просты: декларативное представление ограничений задачи, со­вмещенное с общими методами решения типа хронологического поиска с возвратами или локального поиска.

Программирование в ограничениях имеет множество сильных сторон: мощные языки моделирования, позволяющие представить сложные и дина­мические прикладные задачи; быстрые методы вывода общего назначения типа вынуждения дуговой совместимости, для усечения части пространства поиска; быстрые методы вывода специального назначения, связанные с гло­бальными ограничениями; гибридные методы, сочетающие преимущества методов программирования в ограничениях и подходов исследования опера­ций; методы локального поиска, позволяющие быстро находить решения, близкие к оптимальным; большой диапазон расширений типа мягких огра­ничений и распределенного решения ограничений, с помощью которых воз­можно более адекватное моделирование практических задач.

Логическое программирование в ограничениях

За последние 20 лет программирование в ограничениях прошло путь от научной идеи до мощной парадигмы про­граммирования, которая все больше используется для моделирования и ре­шения многих трудных практически важных задач.

Под программированием в ограничениях (constraint programming) по­нимается программирование алгоритмов решения задач УО. Программирование в ограничениях, считающееся в настоящее время одним из стратегических направлений информатики²⁰, является декла­ративной парадигмой, позволяющей выра­зить многие прикладные задачи с помощью ограничений. Программирование в ограничениях состоит из двух необходимых компонентов: решателя ог­раничений и машины поиска.

Логическое программирование ‑ это парадигма программирования, ос­нованная на логике. Его конструкты ‑ булевы импликации (т.е. илиp:-q), композиций, использующих булевы операции конъюнкции и дизъюнкции. Логическое программирование может рассматриваться как процедурный язык, в котором процедуры ‑ это булевы функции, результат работы программы всегда истина или ложь.

Тот факт, что системы удовлетворения ограничений и логического про­граммирования ‑ декларативные парадигмы, использующие отно­шения и поиск с возвратами, сделал их интеграцию легкой и естественной. Логическое программирование в ограничениях ‑ расширение логиче­ского программиро­вания, в котором унификация может быть заменена или допол­нена другими видами ограничений, определенных на доменах (областях оп­ределения) ис­пользуемых переменных. Схема логического программирова­ния в ограниче­ниях (ЛПО) может рассматриваться как оболочка логического програм­миро­вания, поддерживае­мая системой ограничений, с помощью которой мо­жет записывать и решать любые ограничения. По этой причине схема ЛПО может обозначаться как ЛПО(X), где X определяет класс исполь­зуемых ограниче­ний.

Поскольку описание задачи в виде системы ограничений является декларативным, то при этом описывается, «что» должно выполняться, но не ука­зывается, «как» это сделать.

Общепринятый подход к решению задач УО сочетает дерево поиска с возвратами с распространением ограничений. Это реализовано в системах программирования в ограничениях с конечными доменами, таких как SICStus Prolog, ILOG Solver, и Gecode.

Языки запросов с ограничениями

В области ис­следований взаимосвязи между ЛПО и базами данных (БД) имеются два главных направления. С одной стороны, результаты из теории БД были обобщены и применены для задач УО, что позволило разработать полезные инструменты для проверки некоторых классов задач УО на легкую разрешимость и эффективного решения этих задач. С другой стороны, классические языки обработки запросов в БД были расширены для работы с ограничениями, которые используются не только для установления целостности информации, но также как средство для представления компактным образом множества кортежей БД, приводит к определению БД с ограничениями (Constraint Databases).