Dual Modelling of Permutation and Injection Problems
  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.
