Models of Injection Problems

Abstract

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].