The complexity of valued constraints

该提案是一项合作申请，涉及牛津大学的Peter Jeavons教授、伦敦大学皇家霍洛威学院的David Cohen教授和法国图卢兹第三大学的Martin Cooper博士。我们正在寻求资金来扩展和发展一种新的代数复杂性理论，用于有价值的约束满足问题。约束满足问题存在于调度和电路布局等实际问题中，在计算机科学中得到了广泛的研究。所有已知的算法对于最一般形式的问题都需要指数级的时间，因此对于大的情况是不切实际的。然而，已经确定了几个限制条件，这些限制条件足以使问题的限制形式有效地求解。事实上，对该问题的仔细数学分析表明，任何特定约束满足问题的计算难度与约束的某些代数性质密切相关。在这个研究项目中，我们正在寻求开发一种新的代数方法来解决更广泛的问题，包括约束满足和优化。这样的问题称为值约束问题。我们希望表明，通过使用一般代数方法，我们可以识别所有类型的有值约束，这些约束可以有效地优化。我们还计划在新的软件工具中实现我们开发的技术，这些工具可以用来分析任何给定的有值约束问题的示例，并在适用的情况下使用特定目的的有效方法来解决它。

This proposal is a collaborative application involving Professor Peter Jeavons at the University of Oxford, Professor David Cohen at Royal Holloway, University of London, and Dr Martin Cooper at the University of Toulouse III, France.We are seeking funding to extend and develop a novel algebraic theory of complexity for valued constraint satisfaction problems.Constraint satisfaction problems arise in many practical problems, such as scheduling and circuit layout, so this family of problems has been widely studied in computer science. All known algorithms for the most general form of the problem require exponential time, and are therefore impractical for large cases. However, several restrictions have been identified which are sufficient to make the restricted form of the problem efficiently solvable. In fact, a careful mathematical analysis of the problem has shown that the computational difficulty of any particular constraint satisfaction problem is closely related to certain algebraic properties of the constraints. In this research project we are seeking to develop a new algebraic approach to an even wider class of problems which involve both constraint satisfaction and optimisation. Such problems are called valued constraint problems. We hope to show that by using general algebraic methods we can identify all types of valued constraints which can be efficiently optimised. We also plan to implement the techniques we develop in new software tools which can be use to analyse any given example of a valued constraint problem, and solve it using special-purpose efficient methods when these are applicable.