权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Groebner Basis Techniques for Constraint Satisfaction Problems

约束满足问题的 Groebner 基础技术

基本信息

批准号：
EP/D032636/1
负责人：
Peter Jeavons
金额：
$ 21.33万
依托单位：
University of Oxford
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2006
资助国家：
英国
起止时间：
2006 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FD032636%2F1
关键词：
Groebner Basis Techniques Constraint Satisfaction

项目摘要

Many of the problems we use computers to solve have the same general form: we want the computer to find values for a collection of variables which satisfy various constraints. The constraints restrict the combinations of values allowed for some subsets of the variables. Many difficult computational problems fit this general framework. For example, the problem of scheduling a collection of building tasks in a sensible order, or putting together a timetable for a school or university. The same kinds of problems arise in choosing the frequencies for mobile phone transmitters, choosing the best routes for a fleet of delivery vehicles, or trying to match a newly-discovered protein structure against a database.It has turned out to be very useful for some purposes to view all these different problems as basically the same kind of problem: they can all be seen as constraint satisfaction problems. Doing this has led to the development of special programming languages for this kind of problem, and some very general techniques which allow us to analyse such problems and solve them as efficiently as possible.Some of the most interesting ideas have come from linking problems of this kind to mathematical ideas, such as graph theory, or the idea of an algebra. In this proposal we are seeking to build a new link between constraint satisfaction problems and the area of mathematics that deals with polynomial equations. The combinations allowed by a constraint can be represented as the roots of a polynomial equation, and then the solutions that satisfy a whole set of constraints correspond to the roots of a whole collection of polynomial equations. Mathematicians have developed tools for solving polynomial equations, and manipulating them into simpler forms. We want to see how these ideas can be used to manipulate constraint satisfaction problems. Also, we want to see whether the techniques developed by computer scientists for tackling constraint satisfaction problems and analysing their structure can be used in some new ways to analyse problems involving polynomials. We think that bringing the mathematical ideas together with the computational techniques will give us some new insights into the mathematical ideas, and will help to develop better ways to tackle constraint satisfaction problems.

我们用计算机解决的许多问题都具有相同的一般形式：我们希望计算机为满足各种约束的变量集合找到值。约束限制了某些变量子集允许的值的组合。许多困难的计算问题符合这个一般框架。例如，以合理的顺序安排一系列建筑任务的问题，或者为学校或大学制定时间表的问题。在为移动的电话发射机选择频率、为运输车队选择最佳路线或试图将新发现的蛋白质结构与数据库进行匹配时，也会出现同样的问题，在某些情况下，将所有这些不同的问题视为基本上相同的问题是非常有用的：它们都可以被视为约束满足问题。这样做导致了针对这类问题的特殊编程语言的发展，以及一些非常通用的技术，这些技术使我们能够分析这类问题并尽可能有效地解决它们。一些最有趣的想法来自于将这类问题与数学思想联系起来，如图论或代数的思想。在这个建议中，我们正在寻求建立一个新的约束满足问题之间的联系和处理多项式方程的数学领域。约束所允许的组合可以表示为多项式方程的根，然后满足整个约束集的解对应于整个多项式方程集合的根。数学家们已经开发出了求解多项式方程的工具，并将它们转化为更简单的形式。我们想看看这些想法如何被用来操纵约束满足问题。此外，我们想看看计算机科学家开发的解决约束满足问题和分析其结构的技术是否可以以一些新的方式用于分析涉及多项式的问题。我们认为，将数学思想与计算技术结合起来，将给我们带来一些新的见解的数学思想，并将有助于开发更好的方法来解决约束满足问题。