A Constraint Solver Synthesiser

约束求解器合成器

• 批准号: EP/H004092/1
• 负责人: Ian Miguel
• 金额: $ 118.38万
• 依托单位: University of St Andrews
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2009
• 资助国家: 英国
• 起止时间: 2009 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FH004092%2F1
• 关键词: Constraint; Solver; Synthesiser

Constraints are a natural, powerful means of representing and reasoning about combinatorial problems that impact all of our lives. For example, in the production of a university timetable many constraints occur, such as: the maths lecture theatre has a capacity of 100 students; art history lectures require a venue with a slide projector; no student can attend two lectures at once. Constraint solving offers a means by which solutions to such problems can be found automatically. Its simplicity and generality are fundamental to its successful application in a wide variety of disciplines, such as: scheduling; industrial design; aviation; banking; combinatorial mathematics; and the petrochemical and steel industries, to name but a few examples.Currently, applying constraint technology to a large, complex problem requires significant manual tuning by an expert. Such experts are rare. The central aim of this project is to improve dramatically the scalability of constraint technology, while simultaneously removing its reliance on manual tuning by an expert. We propose a novel, elegant means to achieve this: a constraint solver synthesiser, which generates a constraint solver specialised to a given problem. Synthesising a constraint solver tailored to the needs of an individual problem is a groundbreaking direction for constraints research, which has focused on the incremental improvement of general-purpose solvers. Synthesising a solver from scratch has two key benefits, both of which will have a major impact. First, it will enable a fine-grained optimisation not possible for a general solver, allowing the solution of much larger, more difficult problems. Second, it will open up many exciting research possibilities. There are many techniques in the literature that, although effective in a limited number of cases, are not suitable for general use. Hence, they are omitted from current general solvers and remain relatively undeveloped. The synthesiser will, however, select such techniques as they are appropriate for an input problem, creating novel combinations to produce powerful new solvers. The result will be a dramatic increase in the number of practical problems solvable without the input of a constraints expert.

约束是表示和推理影响我们所有人生活的组合问题的一种自然、强大的方法。例如，在制作大学时间表时会遇到许多限制，比如：数学演讲厅只能容纳100名学生；艺术史课程需要有幻灯片放映机的场地；任何学生都不能同时听两堂课。约束求解提供了一种自动找到此类问题的解决方案的方法。它的简单性和通用性是它在各种学科中成功应用的基础，例如：调度；工业设计；航空；银行；组合数学；以及石油化工和钢铁工业，仅举几个例子。目前，将约束技术应用于大型、复杂的问题需要专家进行大量的手动调整。这样的专家并不多见。该项目的中心目标是显著提高约束技术的可伸缩性，同时消除其对专家手动调整的依赖。我们提出了一种新颖而优雅的方法来实现这一点：约束求解器合成器，它生成专门针对给定问题的约束求解器。综合针对单个问题的需求而定制的约束求解器是约束研究的一个开创性方向，该研究侧重于通用求解器的增量改进。从零开始合成解算器有两个关键的好处，这两个好处都将产生重大影响。首先，它将实现常规求解器无法实现的细粒度优化，从而可以解决更大、更困难的问题。其次，它将开启许多令人兴奋的研究可能性。文献中有许多技术，虽然在有限的情况下有效，但不适合普遍使用。因此，它们在当前的通用求解器中被省略了，并且仍然相对不发达。然而，合成器将选择适合输入问题的技术，创造新的组合来产生强大的新解算器。其结果将是，在没有约束专家投入的情况下，可以解决的实际问题的数量将急剧增加。

项目成果

Breaking Conditional Symmetry in Automated Constraint Modelling with Conjure

使用 Conjure 打破自动约束建模中的条件对称性

• 发表时间: 2014
• 期刊: Proceedings of the 21st European Conference on Artificial Intelligence
• 作者: Akgun, O.

Ethical Issues and Security Monitoring Trends in Global Healthcare - Technological Advancements

全球医疗保健的道德问题和安全监控趋势 - 技术进步

• DOI: 10.4018/978-1-60960-174-4.ch006
• 发表时间: 2011
• 作者: Beratarbide E

An automated approach to generating efficient constraint solvers

生成高效约束求解器的自动化方法

• DOI: 10.1109/icse.2012.6227151
• 发表时间: 2012
• 作者: Balasubramaniam D