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

DOI: 10.37614/2307-5252.2020.8.11.006 УДК 004.832 Ю.А. Олейник1, А.А. Зуенко 1 1 Институт информатики и математического моделирования ФИЦ КНЦ РАН ГЛОБАЛЬНЫЕ ОГРАНИЧЕНИЯ ПРИ МОДЕЛИРОВАНИИ И РЕШЕНИИ ЗАДАЧ В РАМКАХ ПАРАДИГМЫ CONSTRAINT PROGRAMMING* Аннотация На настоящий момент технология программирования ограничений является мощным инструментом решения задач комбинаторного поиска и комбинаторной оптимизации. Для применения данной технологии любая задача должна быть сформулирована как задача удовлетворения ограничений. Роль концепции глобальных ограничений при моделировании и решении прикладных задач в рамках парадигмы программирования ограничений трудно переоценить. Процедуры, реализующие алгоритмы фильтрации глобальных ограничений, являются теми элементарными “кирпичиками”, из которых строится модель конкретной прикладной задачи. Алгоритмы фильтрации глобальных ограничений, как правило, подкреплены соответствующими развитыми теориями, позволяющими организовывать высокопроизводительные вычисления. Выбор той или иной программной библиотеки, прежде всего, обуславливается тем, насколько набор и способ реализации глобальных ограничений соответствует уровню современных исследований в данной области. Основное внимание в настоящей статье сосредоточено на обзоре глобальных ограничений, которые реализованы в рамках наиболее популярных библиотек программирования в ограничениях: Choco, GeCode, JaCoP, MiniZinc. Ключевые слова: программирование ограничений, задача удовлетворения ограничений, глобальные ограничения, алгоритмы фильтрации ограничений. Yu.A. Oleynik1, A.A. Zuenko 1 1 Apatity, Institute for Informatics and Mathematical Modelling, KSC RAS GLOBAL CONSTRAINTS IN MODELING AND SOLVING PROBLEMS WITHIN THE CONSTRAINT PROGRAMMING PARADIGM Abstract At the moment, constraint programming technology is a powerful tool for solving combinatorial search and combinatorial optimization problems. To use this technology, any task must be formulated as a task of satisfying constraints. The role of the concept of global constraints in modeling and solving applied problems within the framework of the constraint programming paradigm can hardly be overestimated. The procedures that implement the algorithms of filtering global constraints are the elementary “building blocks” from which the model of a specific applied problem is built. Algorithms for filtering global constraints, as a rule, are supported by the corresponding developed theories that allow organizing high-performance computing. The choice of a particular software library is primarily determined by the extent to which the set and method of implementing global constraints corresponds to the level of modern research in this area. The main focus of this article is focused on an overview of global constraints that *Исследование выполнено при финансовойподдержке РФФИв рамкахнаучныхпроектов№№ 18- 07-00615-а, 19-07-00359-а, 20-07-00708-a. 67