[计算机科学] 所有不同的、全局基数和相关的分解 制约因素 [推广有奖]

摘要翻译：
我们证明了一些常见的和重要的全局约束，如All-Difference和GCC可以分解成简单的算术约束，在这些算术约束上我们可以实现界或范围的一致性，在某些情况下甚至可以进行更大的剪枝。这些分解可以很容易地添加到新的求解器中。它们还通过共享变量提供了访问传播器状态的其他约束。这种共享可用于改善约束之间的传播。我们报告了在伪布尔求解器中对我们的分解进行的实验。
---
英文标题：
《Decompositions of All Different, Global Cardinality and Related
  Constraints》
---
作者：
Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy
  Quimper and Toby Walsh
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  We show that some common and important global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing of variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.
---
PDF链接：
https://arxiv.org/pdf/0905.3755