Σ-All Different: Softening AllDifferent in Weighted CSPs

A soft version of the well-known global constraint AllDifferent has been recently introduced for the Max-CSP framework ([9, 15, 16]). In this paper, we propose to soften AllDifferent in the Weighted CSP framework that is more general. We extend the two semantics of violation proposed in [9]: the first one is based on variables and the second one on the decomposition into a set of binary constraints of difference. For the first semantic, we propose a polynomial algorithm which maintains hyper- arc consistency. For the second one, we prove that checking hyper-arc consistency is an NP-Hard problem. So, we propose to maintain a local consistency using a filtering based on lower bounds computation. Finally, we present some experimental results and draw a few perspectives.