# Multiplicity-Constraint in Constraint Programming Solvers

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?

• Not sure if this helps, but you could use a binary variable $$x_{i,j} = \begin{cases}1& \text{if x_i=j} \\ 0&\text{otherwise}\end{cases}$$ The multiplicity is then just a summation. Mar 1, 2023 at 15:16

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