RI: Small: Towards Practical Tractability in Constraint Processing

RI：小：实现约束处理的实用易处理性

• 批准号: 1117956
• 负责人: Berthe Choueiry
• 金额: $ 38.56万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117956&HistoricalAwards=false
• 关键词: RI; Small; Towards; Practical; Tractability

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.

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