Задача удовлетворения ограничений 📖 Wikipedia

Задачи удовлетворения ограничений (ЗУО) — это математические задачи, определяемые как набор объектов, состояние которых должно соответствовать ряду ограничений^[англ.] или рамок. ЗУО представляют сущности в задаче как однородную совокупность конечных ограничений над переменными, которые решаются методами удовлетворения ограничений^[англ.]. ЗУО являются предметом исследований как в области искусственного интеллекта и исследования операций, поскольку регулярность их формулировки обеспечивает общую основу для анализа и решения задач из многих, казалось бы, несвязанных семейств. ЗУО часто демонстрируют высокую сложность^[англ.], требуя комбинации эвристических методов^[1] и методов комбинаторного поиска для решения в разумные сроки. Программирование в ограничениях — это область исследований, которая главным образом фокусируется на решении такого рода задач^[2]. Кроме того, задача выполнимости булевых формул, задача выполнимости формул в теориях, смешанное целочисленное программирование и программирование на основе набора ответов — всё это области исследований, сосредоточенные на решении конкретных форм задачи удовлетворения ограничений.

Примеры задач, которые могут быть смоделированы как задача удовлетворения ограничений:

• Вывод типов^[3][4]
• Задача о восьми ферзях^[5] и Задача о ходе коня^[6]
• Задача раскраски карты^[6]
• Выделение частот для систем собильной связи^[6]
• Задача коммивояжёра^[6]
• Задача максимального разреза^[7]
• Судоку, Кроссворды, Футошики, Какуро («пересекающиеся суммы»), Нумератор^[англ.]/Хидато^[англ.], Загадка Эйнштейна и много других логических головоломок.

Эти примеры часто используются в учебных пособиях для решения задач программирования в ограничениях, программирования на основе набора ответов, выполнимости булевых формул и выполнимости формул в теориях. В общем случае задачи с ограничениями могут быть гораздо сложнее и не всегда выразимы в некоторых из этих более простых систем. Примеры из «реальной жизни» включают автоматизированное планирование^[8][9], разрешение лексической многозначности^[10][11], музыковедение^[12], системы «Конфигурация–Цена–Предложение»^{[англ.][13]} и оптимальное распределение ресурсов^[14].

Некоторые задачи искусственного интеллекта и комбинаторной оптимизации, а также некоторые индустриальные применений, обсуждались в терминах ЗУО. К ним относятся задачи планирование, в управление воздушным движением, гражданское строительство, машиностроение, когнитивные процессы, веб-приложения, сетевая безопасность, защита персональных данных или конфиденциальности, и даже контекст осведомлённости^[6].

Существование решения ЗУО может рассматриваться как задача разрешимости. Её можно решить, найдя решение или не найдя его после исчерпывающего поиска (стохастические алгоритмы обычно никогда не приходят к исчерпывающему заключению, в то время как направленные поиски часто это делают на достаточно малых задачах). В некоторых случаях заранее известно, что ЗУО имеет решения, благодаря другому процессу математического вывода.

Формально задача удовлетворения ограничений определяется как тройка ${\displaystyle \langle X,D,C\rangle }$, где^[15]

• ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$ — набор переменных,
• ${\displaystyle D=\{D_{1},\ldots ,D_{n}\}}$ — набор областей значений этих переменных
• ${\displaystyle C=\{C_{1},\ldots ,C_{m}\}}$ — набор ограничений.

Каждая переменная ${\displaystyle X_{i}}$ может принимать значения из непустой области ${\displaystyle D_{i}}$. Каждое ограничение ${\displaystyle C_{j}\in C}$, в свою очередь, является парой ${\displaystyle \langle t_{j},R_{j}\rangle }$, где ${\displaystyle t_{j}\subseteq \{1,2,\ldots ,n\}}$ — набор из ${\displaystyle k}$ индексов, а ${\displaystyle R_{j}}$ — набор ${\displaystyle k}$-арное отношение на соответствующем произведении областей ${\displaystyle \times _{i\in t_{j}}D_{i}}$, где произведение берётся с индексами в возрастающем порядке. Подстановка переменных — это функция из подмножества переменных в определённое множество значений в соответствующем подмножестве областей. Подстановка ${\displaystyle v}$ удовлетворяет ограничению ${\displaystyle \langle t_{j},R_{j}\rangle }$, если значения, присвоенные переменным ${\displaystyle t_{j}}$, удовлетворяют отношению ${\displaystyle R_{j}}$^[16][17].

Подстановка является согласованной, если она не нарушает ни одно из ограничений. Подстановка является полной, если она включает все переменные. Подстановка является решением, если она согласованная и полная^[17].

Задачи удовлетворения ограничений на конечных областях обычно решаются с помощью различных методов поиска. Наиболее распространёнными из них являются варианты поиска с возвратом, методы распространения ограничений^[англ.] и локального поиска. Эти методы часто комбинируются, как, например, в методе «очень крупномасштабного поиска по соседству»^[англ.], а современные исследования включают и другие технологии, такие как линейное программирование^[18].

Поиск с возвратом^[19][20][21] — это рекурсивный алгоритм. Он поддерживает частичное присвоение значений переменным. Изначально все переменные не имеют значений. На каждом шаге выбирается переменная, и ей поочерёдно присваиваются все возможные значения. Для каждого значения проверяется согласованность частичного присвоения с ограничениями. В случае согласованности выполняется рекурсивный вызов. Когда все значения испробованы, алгоритм возвращается назад. В этом базовом алгоритме поиска с возвратом согласованность определяется как выполнение всех ограничений, чьи переменные уже имеют значения. Существует несколько вариантов поиска с возвратом. Проставление обратных отметок^{[англ.][22]} повышает эффективность проверки согласованности. Обратный переход^{[англ.][23][24]} позволяет сэкономить часть поиска, в некоторых случаях возвращаясь назад «более чем на одну переменную». Определения ограничений с помощью обучения^[англ.] выводит и сохраняет новые ограничения, которые могут быть использованы позже для избежания части поиска. Просмотр вперёд^{[англ.][25]} также часто используется в поиске с возвратом для попытки предвидеть последствия выбора переменной или значения, тем самым иногда заранее определяя, когда подзадача является разрешимой или неразрешимой.

Техники распространения ограничений^{[англ.][26][27]} используются для изменения задач удовлетворения ограничений. Точнее, они являются методами, обеспечивающими локальную согласованность^[англ.], которая относится к согласованности группы переменных и/или ограничений. Распространение ограничений имеет несколько применений. Во-первых, оно преобразует задачу в эквивалентную, но обычно более простую для решения. Во-вторых, оно может доказать разрешимость или неразрешимость задач. Это не гарантируется в общем случае, но всегда происходит для некоторых форм распространения ограничений и/или для определённых типов задач. Наиболее известные и используемые формы локальной согласованности — это согласованность по дугам^{[англ.][28][29]}, согласованность по гипердугам^{[англ.][30]} и согласованность по путям^{[англ.][31][32]}. Самый популярный метод распространения ограничений — алгоритм AC-3^{[англ.][33]}, который обеспечивает совместимость по дугам.

Методы локального поиска^[34] — это неполные алгоритмы разрешимости. Они могут найти решение задачи, но могут потерпеть неудачу, даже если задача разрешима. Они работают путём итеративного улучшения полного присвоения значений переменным. На каждом шаге изменяется значение небольшого числа переменных с общей целью увеличения числа ограничений, удовлетворяемых этим присвоением. Алгоритм минимальных конфликтов^{[англ.][35][36]} — это алгоритм локального поиска, специфичный для ЗУО и основанный на этом принципе. На практике локальный поиск хорошо работает, когда эти изменения также зависят от случайного выбора. Была разработана интеграция поиска с локальным поиском, что привело к гибридным алгоритмам^[англ.].

ЗУО также изучаются в теории сложности вычислений, теории конечных моделей^[англ.] и универсальной алгебре. Выяснилось, что вопросы о сложности ЗУО сводятся к важным универсально-алгебраическим вопросам о базовых алгебрах. Этот подход известен как алгебраический подход к ЗУО^[37].

Поскольку любая вычислительная задача разрешимости полиномиально эквивалентна ЗУО с бесконечным шаблоном^[38], общие ЗУО могут иметь произвольную сложность. В частности, существуют ЗУО, относящиеся к классу NP-промежуточных^[англ.] задач, существование которых было продемонстрировано Ладнером^[англ.] при условии, что P ≠ NP.

Однако большой класс ЗУО, возникающих из естественных приложений, удовлетворяет дихотомии сложности, что означает, что каждая ЗУО в этом классе либо принадлежит P либо является NP-полной задачей. Таким образом, эти ЗУО представляют собой одно из крупнейших известных подмножеств NP, которое избегает NP-промежуточных^[англ.] задач. Дихотомия сложности была впервые доказана Шефером^[англ.] для булевых ЗУО, то есть ЗУО с двуэлементной областью и где все доступные отношения являются булевыми операторами. Этот результат был обобщён для различных классов ЗУО, в первую очередь для всех ЗУО с конечными областями. Эта гипотеза о дихотомии для конечных областей была впервые сформулирована Томасом Федером и Моше Варди^[39], а окончательно доказана независимо Андреем Булатовым^[40] и Дмитрием Жуком в 2017 году^[41].

Другие классы, для которых подтверждена дихотомия сложности, включают

• все первого порядка редукции^{[англ.][a]} ${\displaystyle (\mathbb {Q} ,<)}$^[43],
• все первого порядка редукции^[англ.] счётного случайного графа^[44],
• все первого порядка редукции модельного компаньона^[англ.] класса всех C-отношений^[45],
• все первого порядка редукции универсального однородного частично упорядоченного множества^[46],
• все первого порядка редукции однородных неориентированных графов^[47],
• все первого порядка редукции всех унарных структур^[48],
• все ЗУО в классе сложности MMSNP^[49].

Большинство классов ЗУО, которые известны как разрешимые, это те, где гиперграф ограничений имеет ограниченную древовидную ширину^[50][51], или где ограничения имеют произвольную форму, но существуют эквационально нетривиальные полиморфизмы множества отношений ограничений^[52].

Гипотеза дихотомии для бесконечных областей^[53] была сформулирована для всех ЗУО редукций конечных однородных структур, утверждающая, что ЗУО такой структуры находится в P тогда и только тогда, когда её клон полиморфизмов^[англ.] эквационально нетривиален, и в противном случае задача является NP-трудной.

Сложность таких ЗУО, а также других обобщений, (ЗУО с оценками^[54][55][56], кванторная ЗУО^[57][58], «ЗУО с обещаниями») остаётся областью активных исследований^[59].

Любая ЗУО может рассматриваться как задача содержания конъюнктивных запросов^{[англ.][60]}.

Аналогичная ситуация наблюдается между функциональными классами FP^[англ.] и #P. Согласно обобщению теоремы Ладнера^[англ.] существуют задачи, которые не относятся ни к FP, ни к #P-полным^[англ.] задачам, при условии, что FP ≠ #P. Как и в случае с задачами разрешимости, задача в #ЗУО определяется набором отношений. Каждая задача принимает на вход булеву формулу, и цель состоит в вычислении количества удовлетворяющих присваиваний. Это можно дополнительно обобщить, используя большие размеры доменов и присваивая вес каждому удовлетворяющему присваиванию, а затем вычисляя сумму этих весов. Известно, что любая сложная взвешенная задача #ЗУО либо относится к FP, либо является #P-трудной^[61].

Классическая модель задачи удовлетворения ограничений определяет модель статических, негибких ограничений. Эта жёсткая модель является недостатком, затрудняющим простое представление задач^[62]. Было предложено несколько модификаций базового определения ЗУО для адаптации модели к широкому кругу задач.

Динамические ЗУО^[63][64] (ДЗУО) полезны, когда исходная формулировка задачи каким-либо образом изменяется, обычно потому, что набор рассматриваемых ограничений меняется из-за окружающей среды^[65]. ДЗУО рассматриваются как последовательность статических ЗУО, каждая из которых является преобразованием предыдущей, в которой переменные и ограничения могут быть добавлены (усиление ограничений) или удалены (ослабление ограничений)^[66]. Информация, найденная в исходных формулировках задачи, может быть использована для уточнения последующих. Метод решения может быть классифицирован в соответствии со способом передачи информации:

• Оракулы^[67]: решения, найденные для предыдущих ЗУО в последовательности, используются как эвристики для решения текущей задачи ЗУО с нуля.
• Локальное исправление^[68]: каждая ЗУО рассчитывается, начиная с частичного решения предыдущей, и исправляет несогласованные ограничения с помощью локального поиска.
• Запись ограничений^[69]: на каждом этапе поиска определяются новые ограничения, чтобы отразить усвоение несовместимых групп решений. Эти ограничения переносятся на новые задачи ЗУО.

Классические ЗУО рассматривают ограничения как жёсткие, то есть они обязательны (каждое решение должно им соответствовать) и негибкие (в том смысле, что они должны быть полностью удовлетворены, иначе они полностью нарушены). Гибкие ЗУО ослабляют эти предположения, частично ослабляя ограничения и позволяя решению не соответствовать всем из них^[70]. Это похоже на предпочтения в планировании, основанном на предпочтениях^[англ.]. Некоторые типы гибких задач ЗУО включают:

• MAX-ЗУО^[71][72], допускается нарушение некоторого количества ограничений, а качество решения измеряется количеством удовлетворённых ограничений.
• Взвешенные ЗУО^{[англ.][73]} — это, MAX-ЗУО, в котором каждое нарушение ограничения взвешивается в соответствии с заранее определённым предпочтением. Удовлетворение ограничения с бо́льшим весом является предпочтительным.
• Нечёткие ЗУО^[74] моделируют ограничения как нечёткие отношения, в которых удовлетворение ограничения является непрерывной функцией значений его переменных, варьируясь от полностью удовлетворённого до полностью нарушенного.

В ДЗУО^[75][76][b] каждая переменная ограничения рассматривается как имеющая отдельное географическое положение. Строгие ограничения накладываются на обмен информацией между переменными, требующие использования полностью распределённых алгоритмов для решения задачи удовлетворения ограничений.

• Составной граф ограничений^[англ.]
• Программирование в ограничениях
• Декларативное программирование
• Условный экстремум
• Задача оптимизации с распределёнными ограничениями^[англ.]
• Гомоморфизм графов
• Гипотеза об уникальных играх^[англ.]
• Задача удовлетворения взвешенных ограничений^[англ.]

• Christophe Lecoutre. Constraint Networks: Techniques and Algorithms. — Wiley, 2013. — ISBN 978-1-118-61791-5.
• Satish Chandra, Colin S. Gordon, Jean-Baptiste Jeannin, Cole Schlesinger, Manu Sridharan, Frank Tip, Youngil Choi. Type inference for static compilation of JavaScript // Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications. — 2016. — ISBN 978-1-4503-4444-9. — doi:10.1145/2983990.2984017.
• Malik Ghallab, Dana Nau, Paolo Traverso. Automated Planning: Theory and Practice. — Elsevier, 2004. — ISBN 978-0-08-049051-9.
• George C. Demetriou. Lexical disambiguation using constraint handling in Prolog (CHIP)] // Proceedings of the sixth conference on European chapter of the Association for Computational Linguistics. — Association for Computational Linguistics, 1993. — ISBN 978-90-5434-014-0.
• Maryellen C. MacDonald, Mark S. Seidenberg. Constraint satisfaction accounts of lexical and sentence comprehension // Handbook of Psycholinguistics (Second Edition). — ELSEVIER, 2006. — ISBN 9780123693747.
• Mauricio Toro, Carlos Agon, Camilo Rueda, Gerard Assayag. GELISP: A FRAMEWORK TO REPRESENT MUSICAL CONSTRAINT SATISFACTION PROBLEMS AND SEARCH STRATEGIES // Journal of Theoretical and Applied Information Technology. — 2016. — Т. 86, вып. 2.
• Dong Yang, Ming Dong. Applying constraint satisfaction approach to solve product configuration problems with cardinality-based configuration rules // Journal of Intelligent Manufacturing. — 2013. — Т. 24.
• Pragnesh Jay Modi, Hyuckchul Jung, Milind Tambe, Wei-Min Shen, Shriniwas Kulkarni. A dynamic distributed constraint satisfaction approach to resource allocation // International Conference on Principles and Practice of Constraint Programming. — Berlin, Heidelberg: Springer, 2001.
• Stuart Jonathan Russell, Peter Norvig. Artificial Intelligence: A Modern Approach. — Prentice Hall, 2010. — ISBN 9780136042594.
• Hybrid optimization : the ten years of CPAIOR // International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimisation Problems / (ed) Michela Milano, Pascal Van Hentenryck. — New York: Springer, 2011. — ISBN 9781441916440. — OCLC 695387020.
• Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik, Dmitriy Zhuk. Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras // Theoretics. — 2024. — Т. 3. — ISSN 2751-4838. — doi:10.46298/theoretics.24.14. — arXiv:2104.11808. article-number:11361
• Tomás Feder, Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory (англ.) // SIAM Journal on Computing. — 1998. — Vol. 28, iss. 1. — P. 57–104. — ISSN 0097-5397. — doi:10.1137/S0097539794266766.
• Andrei Bulatov. A Dichotomy Theorem for Nonuniform CSPs // Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017. — IEEE Computer Society, 2017. — ISBN 978-1-5386-3464-6. — doi:10.1109/FOCS.2017.37. — arXiv:1703.03021.
• Dmitriy Zhuk. A Proof of the CSP Dichotomy Conjecture // Journal of the ACM. — 2020. — Т. 67. — doi:10.1145/3402029. — arXiv:1704.01914.
• Manuel Bodirsky, Jan Kára. The complexity of temporal constraint satisfaction problems // J. ACM. — 2010. — Т. 57, вып. 2. — ISSN 0004-5411. — doi:10.1145/1667053.1667058.
• Michael Pinsker, Manuel Bodirsky. Schaefer's theorem for graphs // Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11). — Association for Computing Machinery, 2011. — С. 655–664. — ISBN 978-1-4503-0691-1. — doi:10.1145/1993636.1993724. — arXiv:1011.2894.
• Manuel Bodirsky, Peter Jonsson, Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction Problems // ACM Trans. Comput. Logic. — 2017. — Т. 18, вып. 3. — ISSN 1529-3785. — doi:10.1145/3105907. — arXiv:1503.07310.
• Michael Kompatscher, Trung Van Pham. A Complexity Dichotomy for Poset Constraint Satisfaction // 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (англ.). — Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. — Vol. 66. — (Leibniz International Proceedings in Informatics). — ISBN 978-3-95977-028-6. — doi:10.4230/LIPIcs.STACS.2017.47.
• Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz. Constraint Satisfaction Problems for Reducts of Homogeneous Graphs (англ.) // SIAM Journal on Computing. — 2019. — January (vol. 48, iss. 4). — ISSN 0097-5397. — doi:10.1137/16M1082974. — arXiv:1602.05819.
• Manuel Bodirsky, Antoine Mottet. A Dichotomy for First-Order Reducts of Unary Structures // Logical Methods in Computer Science. — 2018. — Т. 14, вып. 2. — doi:10.23638/LMCS-14(2:13)2018. — arXiv:1601.04520. article-number:3264
• Manuel Bodirsky, Florent Madelaine, Antoine Mottet. A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP // Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. — New York, NY, USA: Association for Computing Machinery, 2018. — (LICS '18). — ISBN 978-1-4503-5583-4. — doi:10.1145/3209108.3209156. — arXiv:1802.03255.
• Libor Barto, Marcin Kozik. Constraint Satisfaction Problems Solvable by Local Consistency Methods // J. ACM. — 2014. — Т. 61, вып. 1. — С. 3:1–3:19. — ISSN 0004-5411. — doi:10.1145/2556646.
• Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction. — Cambridge: Cambridge University Press, 2021. — (Lecture Notes in Logic). — ISBN 978-1-107-04284-1.
• Manuel Bodirsky, Michael Pinsker, András Pongrácz. Projective Clone Homomorphisms (англ.) // The Journal of Symbolic Logic. — 2021. — March (vol. 86, iss. 1). — P. 148–161. — ISSN 0022-4812. — doi:10.1017/jsl.2019.23. — arXiv:1409.4601.
• Phokion G. Kolaitis, Moshe Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction // Journal of Computer and System Sciences. — 2000. — Т. 61, вып. 2. — doi:10.1006/jcss.2000.1713.
• Jin-Yi Cai, Xi Chen. Complexity of counting CSP with complex weights // Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12). — 2012. — ISBN 978-1-4503-1245-5. — doi:10.1145/2213977.2214059. — arXiv:1111.2384.
• Dechter R., Dechter A. Belief Maintenance in Dynamic Constraint Networks // Proceedings of the 7th National Conference on Artificial Intelligenc. — 1988. — [Архивировано 17 ноября 2012 года.]
• Gkrard Verfaillie, Thomas Schiex. Solution reuse in dynamic constraint satisfaction problems // Proceedings of the 12th National Conference on Artificial Intelligence. — 1994. — Т. 1. — ISBN 0262510782.
• Duffy K.R., Leith D.J. IEEE/ACM Transactions on Networking, 21(4). — 2013. — Август (т. 21, вып. 4). — doi:10.1109/TNET.2012.2222923. — arXiv:1103.3240.
• Manuel Bodirsky, Martin Grohe. Non-dichotomies in Constraint Satisfaction Complexity // Automata, Languages and Programming (англ.) / (ed)Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz. — Berlin, Heidelberg: Springer, 2008. — Vol. 5126. — (Lecture Notes in Computer Science). — ISBN 978-3-540-70583-3. — doi:10.1007/978-3-540-70583-3_16.
• Handbook of Constraint Programming / (ed) Francesca Rossi, Peter van Beek, Toby Walsh. — ELSEVIER, 2006. — (Foundations of Artificial Intelligence). — ISBN 978-0-444-52726-4.
• Э. Э. Гасанов, Д.Н. Бабин, А.В. Галатенко, Д.Н. Жук, Г.В. Калачев, П.А. Пантелеев, А.А. Часовских. МаТИС – ШКОЛА В.Б. КУДРЯВЦЕВА: ТРАДИЦИИ И РАЗВИТИЕ // вестн. моск. ун-та.. — 2024. — № 6.
• Krzysztof R. Apt. Principles of Constraint Programming. — Cambridge University Press, 2003. — ISBN 978-0-521-82583-2.
• Olga Kosheleva, Martine Ceberio, Vladik Kreinovich. Adding Constraints – A (Seemingly Counterintuitive but) Useful Heuristic in Solving Difficult Problems // Constraint Programming and Decision Making / Martine Ceberio, Vladik Kreinovich Editors. — Springer, 2014. — Т. 539. — С. 79. — (Studies in Computational Intelligence). — ISBN 978-3-319-04279-4. Замечание: Нужно помнить, что во многих практических ситуациях упрощённые модели, позволяющие приблизительно оценить качество различных решений, приводят к далеко не оптимальным результатам при поиске оптимального решения (статья тех же авторов «Simplicity Is Worse Than Theft: A Constraint-Based Explanation of a Seemingly Counter-Intuitive Russian Saying»).
• Khaled Ghédira. Constraint Satisfaction Problems. — WILEY, 2013. — (Computer Engineering and IT series). — ISBN 978-1-84821-460-6.

• A quick introduction to constraint satisfaction on YouTube
• Manuel Bodirsky (2021). Complexity of Infinite-Domain Constraint Satisfaction. Cambridge University Press. https://doi.org/10.1017/9781107337534
• Steven Minton, Andy Philips, Mark D. Johnston, Philip Laird. Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems // Journal of Artificial Intelligence Research. — 1993. — Т. 58, вып. 1–3. — P. 161–205. — doi:10.1016/0004-3702(92)90007-k.
• Edward Tsang. Foundations of Constraint Satisfaction. — Academic Press, 1993. — ISBN 0-12-701610-4.
• Hubie Chen. A Rendezvous of Logic, Complexity, and Algebra // ACM Computing Surveys. — Декабрь (т. 42, вып. 1). — С. 1–32. — doi:10.1145/1592451.1592453. — arXiv:cs/0611018.
• Rina Dechter. Constraint processing. — Morgan Kaufmann, 2003. — ISBN 1-55860-890-7.
• Krzysztof Apt. Principles of constraint programming. — Cambridge University Press, 2003. — ISBN 9780521825832.
• Christophe Lecoutre. Constraint Networks: Techniques and Algorithms. — ISTE/Wiley, 2009. — ISBN 978-1-84821-106-3.
• Tomás Feder, Constraint satisfaction: a personal perspective, manuscript.
• Constraints archive
• Forced Satisfiable CSP Benchmarks of Model RB Архивировано 25 января 2021 года.
• Benchmarks – XML representation of CSP instances
• XCSP3 – An XML-based format designed to represent CSP instances
• Constraint Propagation – Dissertation by Guido Tack giving a good survey of theory and implementation issues