Dual Modelling of Permutation and Injection Problems
Dual Modelling of Permutation and Injection Problems
复制标题
排列和注入问题的对偶建模
DOI：
--
复制
发表时间：
2011
影响因子：
5
通讯作者：
T. Walsh
中科院分区：
文献类型：
--
作者：
Brahim Hnich;B. Smith;T. Walsh
在编写约束程序时，我们必须选择哪些变量应该作为决策变量，以及如何表示对这些变量的约束。在许多情况下，决策变量有相当多的选择。例如，考虑排列问题，其中我们有与变量一样多的值，并且每个变量都有一个唯一的值。在此类问题中，我们可以在原始观点和双重观点之间进行选择。在对偶观点中，每个对偶变量代表原始值之一，而每个对偶值代表原始变量之一。或者，通过通道约束来链接原始变量和对偶变量，我们可以拥有包含两组变量的组合模型。在本文中，我们对两类问题的原始、对偶和组合模型进行了广泛的理论和实证研究：排列问题和注入问题。我们的结果表明，使用多个观点通常是有利的，并在它们之间建立约束以保持一致性。它们还说明了比较不同约束模型的通用方法。
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 represemts one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combines model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combines models for two classes of problems: permutation problems and injection problems. Our results show that if 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.