RI: Small: Towards Practical Tractability in Constraint Processing

人工智能、工程和管理中的许多问题都可以作为约束满足问题进行建模和解决，但在实践中，可扩展性仍然是成功部署约束求解器的主要障碍。该项目的目标是设计算法和策略，使计算机能够在实践中克服可伸缩性障碍。为此，本文提出的研究目标是约束处理中最有希望打破复杂性障碍的两个基本机制，即增强一致性和检测和打破对称性。本项目旨在为这两种机制设计新的算法，并制定将它们交织在一起的策略。问题的可处理性是由问题的结构参数与其一致性水平之间的关系来保证的。该项目旨在设计算法，在不不利地修改问题结构的情况下强制执行所需的一致性级别。可以检测和利用对称性，从而大大降低解决问题的成本。本项目旨在(1)设计用于检测对称性的算法，以及(2)在不牺牲问题解决的可靠性和完整性的情况下开发利用对称性的近似策略。一个关键的观察是，用于增强一致性的算法和用于局部检测对称性的算法基于相同的原子操作。此外，它们在互补的操作条件下似乎是有效的。本项目进一步旨在设计策略，将两种类型的算法交织在一起，使一种类型的应用能够促进另一种类型的应用，从而产生新的机会来控制组合爆炸。该方法将在实际应用中得到验证，并扩展到计算机科学的其他领域（如数据库和软件工程）中解决类似的组合问题。这些活动有助于对约束加工的两个基本方面的研究取得进展。从实践的角度来看，本研究直接有利于许多具有实际意义的组合问题。从科学的角度来看，该项目将确定与其他计算机科学领域（如数据库和软件工程）的联系，并建立新的桥梁。从这些调查中获得的见解将用于改进约束处理入门和高级课程的范围和内容。这些机会和研究途径将被大量利用，让本科生参与研究，并让他们在使用项目对他们感兴趣的问题（例如数独）的见解方面获得经验，并让他们理解计算机科学课程中算法的操作；目标是激励学生进行约束处理的研究，并将该领域的成果传递给计算机科学、数学、工程等领域的其他学生和研究人员，吸引高中生学习计算机科学，此外，向公众解释一些复杂问题解决的核心基本机制。

Many problems in artificial intelligence, engineering, and management can be advantageously modeled and solved as Constraint Satisfaction Problems, but scalability remains in practice a major obstacle to the successful deployment of Constraint Solvers. The goal of this project is to design algorithms and strategies that enable computers to overcome, in practice, the scalability barrier. To this end, the proposed research targets the two fundamental mechanisms in Constraint Processing that are the most promising for breaking the complexity barrier, namely, enforcing consistency and detecting and breaking symmetry. This project aims to design new algorithms for those two mechanisms and develop strategies for intertwining them. The tractability of a problem is guaranteed by a relationship between a structural parameter of the problem and its level of consistency. This project aims to design algorithms that enforce the needed level of consistency without adversely modifying the structure of the problem. Symmetries can be detected and exploited to dramatically reduce the cost of problem solving. This project aims to (1) design algorithms for detecting symmetries, and (2) develop approximation strategies for exploiting them without sacrificing the soundness and completeness of problem solving. A key observation is that algorithms for enforcing consistency and those for locally detecting symmetry are based on the same atomic operations. Furthermore, they seem to be effective under complementary operating conditions. This project further aims to design strategies for intertwining the operation of the two types of algorithms so that the application of the one type enables and facilitates that of the other type, in order to yield new opportunities to control the combinatorial explosion. The approach will be validated on applications of practical importance and extended to address similar combinatorial problems in other areas of Computer Science such as Databases and Software Engineering.The proposed activities contribute to the progress of the research on two fundamental aspects of Constraint Processing. From a practical perspective, this research directly benefits many combinatorial problems of practical importance. From a scientific standpoint, this project will identify connections and build new bridges with other areas of Computer Science, such as Databases and Software Engineering. The insight gained from these investigations will be used to improve the scope and content of introductory and advanced courses on Constraint Processing. The opportunities and research avenues will be heavily exploited to involve undergraduate students in research and to give them experience in using the project's insights on problems that they find engaging (e.g., Sudoku) and for understanding the operation of algorithms in Computer Science courses; the goal is to motivate students to conduct research in Constraint Processing and to transfer results from this field to other students and researchers in Computer Science, Mathematics, Engineering, to entice high-school students to study Computer Science, and in addition, to explain to the general public some of the fundamental mechanisms at the heart of complex problem solving.