摘要翻译:
在编写约束程序时,我们必须选择哪些变量应该是决策变量,以及如何表示这些变量上的约束。在许多情况下,决策变量有相当大的选择余地。例如,考虑置换问题,其中我们的值和变量一样多,每个变量都有一个唯一的值。在这样的问题上,我们可以在原始观点和双重观点之间做出选择。在对偶视点中,每个对偶变量表示一个原始值,而每个对偶值表示一个原始变量。或者,通过引导约束来连接原始变量和对偶变量,我们可以有一个包含两组变量的组合模型。在本文中,我们对两类问题:置换问题和注入问题的原始模型、对偶模型和组合模型进行了广泛的理论和实证研究。我们的结果表明,使用多个视点往往是有利的,并对它们之间的通道进行约束以保持一致性。它们还说明了比较不同约束模型的一般方法。
---
英文标题:
《Dual Modelling of Permutation and Injection Problems》
---
作者:
B. Hnich, B. M. Smith, T. Walsh
---
最新提交年份:
2011
---
分类信息:
一级分类: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中的材料。
--
---
英文摘要:
When writing a constraint program, we have to choose which variables should be the decision variables, and how to represent the constraints on these variables. In many cases, there is considerable choice for the decision variables. Consider, for example, permutation problems in which we have as many values as variables, and each variable takes an unique value. In such problems, we can choose between a primal and a dual viewpoint. In the dual viewpoint, each dual variable represents one of the primal values, whilst each dual value represents one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combined model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combined models for two classes of problems: permutation problems and injection problems. Our results show that it often be advantageous to use multiple viewpoints, and to have constraints which channel between them to maintain consistency. They also illustrate a general methodology for comparing different constraint models.
---
PDF链接:
https://arxiv.org/pdf/1107.0038