Hybrid tractability of valued constraint problems
Hybrid tractability of valued constraint problems
复制标题
DOI：
10.1016/j.artint.2011.02.003
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
Martin C. Cooper;Stanislav Živný
中科院分区：
文献类型：
--
作者：
Martin C. Cooper;Stanislav Živný
约束满足问题（CSP）是计算机科学和人工智能中的一个核心通用问题：它为许多理论问题和许多实际应用提供了一个通用框架。有值约束问题是CSP的一种推广，它允许用户对优化问题建模。在确定确保此类问题可处理性的特性方面已经作出了相当大的努力。在这项工作中，我们开始研究有值约束问题的混合可跟踪性；也就是说，保证给定值约束问题的可追溯性的属性，但它不仅依赖于实例的底层结构（如树结构），也不依赖于实例中的值约束类型（如子模块化）。我们提出了几种允许所有一元约束的有值约束问题的新混合类，包括机器调度问题、无重叠无货的任意点约束问题和具有任意一元约束的softalldiffconstraint。我们研究的一个重要工具是禁止子结构的概念。
The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and theSoftAllDiffconstraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.