Труды КНЦ вып. 11 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 8/2020 (11)

are implemented within the most popular constraint programming libraries: Choco, GeCode, JaCoP, MiniZinc. constraint programming, constraint satisfaction problem, global constraints, constraint filtering algorithms. Введение На настоящий момент технология программирования ограничений (Constraint Programming - CP) является мощным инструментом решения задач комбинаторного поиска и комбинаторной оптимизации. Для применения данной технологии любая задача должна быть сформулирована как задача удовлетворения ограничений (CSP - Constraint Satisfaction Problem). Задача удовлетворения ограничений состоит из трех компонент: < X, D, C>. X - множество переменных {X 1 ,X 2 , ..., Xn}. D - множество доменов {D 1 , D 2 , ..., Dn}, где Di является доменом (областью определения) переменной Xi. C - множество ограничений {C 1 , C 2 , ..., Cm}, которые предписывают допустимые комбинации значений переменных. Каждый домен Di описывает множество допустимых значений {v 1 , ..., vk} для переменной Xi. Под ограничением понимается любое соотношение между переменными предметной области. В качестве ограничений могут выступать арифметические выражения; логические формулы; таблицы; выражения, формулируемые на языке специализированных теорий. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям. В некоторых случаях необходимо получить все решения. Иногда требуется найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. CSP-задачи принадлежат классу NP-полных задач. Технология программирования в ограничениях предоставляет мощные и гибкие методы, алгоритмы решения задач комбинаторного поиска. Особенности технологии: 1. С точки зрения конечного пользователя задача CSP формулируется в декларативном виде, на языке близком к языку математики. Порядок задания ограничений несущественен. 2. Любой алгоритм удовлетворения ограничений должен содержать две обязательных компоненты: а) компоненту, реализующую вывод (распространение); б) компоненту, реализующую поиск. 3. Вывод (распространение) реализуется как целенаправленное сужение изначально заданных областей определения переменных. 4. Эвристики, используемые в процедурах поиска, разрабатываются не под конкретную задачу, а являются универсальными. 5. Благодаря архитектуре систем программирования в ограничениях, появляется возможность совместно обрабатывать количественные и качественные ограничения. 6. Обеспечивается возможность сопровождать модели, отрытые для оперативных модификаций, то есть развивающиеся модели. При добавлении/удалении из модели ограничений нет необходимости писать новые методы решения задачи. Keywords: 68