Глобальные ограничения

Задачи удовлетворения ограничений с конечными доме­нами используют глобальные ограничения. Глобальное ограничение ‑ это ог­раничение над подмножеством переменных (пример – ограничение all-different). У глобальных ограничений есть два преимущества. Во-первых, гло­бальные ограничения облегчают задачу моделирования прикладной про­блемы в виде ЗУО. Во-вторых, можно разработать алгоритм распространения ограничений[5] специального вида, учитывающий особенности ограничения и поэтому намного более эффективный. Классическим примером глобального ограничения служит all-different ‑ ограничение, которое определяет, что пе­ременные должны быть попарно различными.

Помимо ''all-different'', типичным примером служат ограничение ''atmost'', устанавливающее лимит на число переменных с определенным зна­чением, а также кумулятивное ограничение и кардинальное ограничение, ис­пользуемые при составлении расписаний, упорядочении работ и в календар­ном планировании. Глобальное кардинальное ограничение над множеством переменных и значений определяет условие, что число переменных, которым присвоены значения, должно быть между данными верхней и нижней грани­цами, причем эти границы могут быть различны для каждого значения. Ку­мулятивное ограничение над множеством переменных, представляющих время выполнения различных работ, гарантирует, что работы упорядочены так, что в любое время , не превышаются имеющиеся в наличии величины ресурсов.

Мягкие ограничения

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

Многие прикладные задачи УО обычно являются переограниченными (overconstrained), в которых задано слишком много ограничений, так что невозможно все их одновременно удовлетворить. В таких случаях, вначале нужно выяснить, имеются ли решения задачи УО вообще[6], а затем нужно решить, какие из ограничений ослабить, чтобы задача стала разрешимой.

В связи с этим было введено понятие мягкого ограничения (soft constraint): мягкое ограничение ‑ это само ограничение плюс его дополни­тельная характеристика (критерий), которая может интерпретироваться как стоимость, уровень важности, степень неопределенности или нечто подобное. Нахождение решения не означает далее нахождение такового, удовлетво­ряющего всем ограничениям, но получение значений переменных, для кото­рых достигается «наилучшее» значение для выбранного критерия.