1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 1 at 15:16

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Completely agree. This is another exotic variation on global cardinality. Just encode it with Boolean variables. Even better, do not use integer variables at all, just arrays of Boolean variables. $\endgroup$ Mar 1 at 18:42

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.