Multiplicity-Constraint in Constraint Programming Solvers

Question

I need to solve a CSP with a constraint imposing upper bounds on the multiplicity of variables in a list. More precisely, I need a constraint of the form multiplicity(VARIABLES,UPPER_BOUNDS), where VARIABLES is a list of $n$ variables and UPPER_BOUNDS is a list of $n$ (constant) integers, so that the constraint is satisfied if at most UPPER_BOUNDS[i] variables take the same value as VARIABLES[i], for $i=1,\ldots,n$.

For example, multiplicity([1,2,2,3,2,1],[2,3,4,1,3,3]) is satisfied but multiplicity([1,2,2,3,2,1],[2,2,4,1,3,3]) fails because the second variable (equal to 2) appears 3 times in the list but has a multiplicity bounded by 2.

1. I wonder if there is an out-of-the box constraint available in any CP solver to do that?

2. I am aware of the constraint 𝚊𝚝𝚖𝚘𝚜𝚝(𝙽,𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂,𝚅𝙰𝙻𝚄𝙴) (cf. this ref), which demands that at most N variables in the list VARIABLES take the value VALUE. What I need is thus a generalization of atmost allowing the VALUE to be a variable. Then, the multiplicity constraint could be written as atmost(UPPER_BOUND[i],VARIABLES,VARIABLES[i]), for $i=1,\ldots,n$. Is there a CP solver supporting a variant of atmost allowing a variable in the field VALUE ?

3. At the moment, my best guess was to rewrite the multiplicity constraint as a list of implications VARIABLES[i]=j implies atmost(UPPER_BOUND[i],VARIABLES,j) , for all $i=1,\ldots,n$ and all values $j$ that the variables can take. In practice the pruning does not seem to be very efficient with this approach. Is there another get-around that would be more efficient?

Answer 1

What "special" constraints a CP solver provides tends to vary by solver. I think it is fairly common, though, for CP solvers to treat logical expressions as equivalent to binary variables. So if $x[]$ is your vector of variables and $b[]$ your vector of upper bounds, you could write something like $\sum_{j\neq i}(x[i] == x[j]) \le b[i].$