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.
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 mostN
variables in the listVARIABLES
take the valueVALUE
. What I need is thus a generalization ofatmost
allowing theVALUE
to be a variable. Then, the multiplicity constraint could be written asatmost(UPPER_BOUND[i],VARIABLES,VARIABLES[i])
, for $i=1,\ldots,n$. Is there a CP solver supporting a variant ofatmost
allowing a variable in the fieldVALUE
?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?