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
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$.
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.
I wonder if there is an out-of-the box constraint available in any CP solver to do that?
I am aware of the constraint
𝚊𝚝𝚖𝚘𝚜𝚝(𝙽,𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂,𝚅𝙰𝙻𝚄𝙴)(cf. this ref), which demands that at most
Nvariables in the list
VARIABLEStake the value
VALUE. What I need is thus a generalization of
VALUEto 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
atmostallowing a variable in the field
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?