  In many combinatorial problems one may need to model the diversity or
similarity of assignments in a solution. For example, one may wish to maximise
or minimise the number of distinct values in a solution. To formulate problems
of this type, we can use soft variants of the well known AllDifferent and
AllEqual constraints. We present a taxonomy of six soft global constraints,
generated by combining the two latter ones and the two standard cost functions,
which are either maximised or minimised. We characterise the complexity of
achieving arc and bounds consistency on these constraints, resolving those
cases for which NP-hardness was neither proven nor disproven. In particular, we
explore in depth the constraint ensuring that at least k pairs of variables
have a common value. We show that achieving arc consistency is NP-hard, however
achieving bounds consistency can be done in polynomial time through dynamic
programming. Moreover, we show that the maximum number of pairs of equal
variables can be approximated by a factor 1/2 with a linear time greedy
algorithm. Finally, we provide a fixed parameter tractable algorithm with
respect to the number of values appearing in more than two distinct domains.
Interestingly, this taxonomy shows that enforcing equality is harder than
enforcing difference.
