There are many problems that can be modelled as injection problems. These problems can be scheduling problems, combinatorial
graph problems, cryptarithmetic puzzles, etc. Injection problems can be modelled as constraint satisfaction problems. The
straightforward formulation would be to have as many variables as the elements of the source set that range over the target
set, which captures a total function. To enforce that the function is injective, we would need to state an alldifferent constraint
among all the variables. Dual variables can also be used along with the primal ones and linked through channeling constraints.
We propose three different ways of achieveing this, as well as we add some implied constraints. The proposed models of injection
problems are compared using the constraint tightness parameterized by the level of local consistency being enforced [2]. We proved that, with respect to arc-consistency a single primal alldifferent constraint is tighter than channeling constraints
together with the implied or the dual not-equals constraints, but that the channeling constraints alone are as tight as the
primal not-equals constraints. Both these gaps can lead to an exponential reduction in search cost when MAC or MGAC are used.
The theoretical results showed that occurs constraints on dual variables are redundant, so we can safely discard them. The
asymptotic analysis added details to the theoretical results. We conclude that it is safe to discard some of the models because
they achieve less pruning than other models at the same cost. However, we keep a model employing primal and dual variables
even though it achieves the same amount of pruning as a primal model at a higher cost because it might allow the development
of cheap value ordering heuristics. Experimental results on a sport scheduling problem confirmed that MGAC on channeling and
implied constraints outperformed MAC on primal not-equals constraints, and could be competitive with maintaining GAC on a
primal alldifferent constraint.
Full version of this work can be found at [1].