MiniZinc 中的基数约束

Question

MiniZinc constraint solver allows to express cardinality constraints 很容易使用内置的 sum() 函数：

%  This predicate is true, iff 2 of the array
%  elements are true
predicate exactly_two_sum(array[int] of var bool: x) =
    (sum(x) == 2);

满足基数约束条件，当且仅当布尔变量数组中的 true 元素数与指定的相同。布尔值自动映射到整数值 0 和 1 以计算总和。

我将自己的基数约束谓词实现为一组计数器切片：

%  This predicate is true, iff 2 of the array
%  elements are true
predicate exactly_two_serial(array[int] of var bool: x) =
    let 
    {
      int: lb = min(index_set(x));
      int: ub = max(index_set(x));
      int: len = length(x);
    }
    in
    if len < 2 then
      false
    else if len == 2 then
      x[lb] /\ x[ub]
    else
      (
        let 
        {
          %  1-of-3 counter is modelled as a set of slices
          %  with 3 outputs each
          array[lb+1..ub-1] of var bool: t0;
          array[lb+1..ub-1] of var bool: t1;
          array[lb+1..ub-1] of var bool: t2;
        }
        in
        %  first two slices are hard-coded
        (t0[lb+1] == not(x[lb] \/ x[lb+1])) /\
        (t1[lb+1] == (x[lb] != x[lb+1])) /\
        (t2[lb+1] == (x[lb] /\ x[lb+1])) /\
        %   remaining slices are regular
        forall(i in lb+2..ub-1)
        (
          (t0[i] == t0[i-1] /\ not x[i]) /\
          (t1[i] == (t0[i-1] /\ x[i]) \/ (t1[i-1] /\ not x[i])) /\
          (t2[i] == (t1[i-1] /\ x[i]) \/ (t2[i-1] /\ not x[i])) 
        ) /\
        %  output 2 of final slice must be true to fulfil predicate
        ((t1[ub-1] /\ x[ub]) \/ (t2[ub-1] /\ not x[ub]))
      )
    endif endif;

此实现使用并行编码，切片之间 lines/variables 较少：

%  This predicate is true, iff 2 of the array
%  elements are true
predicate exactly_two_parallel(array[int] of var bool: x) =
    let 
    {
      int: lb = min(index_set(x));
      int: ub = max(index_set(x));
      int: len = length(x);
    }
    in
    if len < 2 then
      false
    else if len == 2 then
      x[lb] /\ x[ub]
    else
      (
        let 
        {
          %  counter is modelled as a set of slices
          %  with 2 outputs each
          %  Encoding:
          %  0 0 : 0 x true
          %  0 1 : 1 x true
          %  1 0 : 2 x true
          %  1 1 : more than 2 x true
          array[lb+1..ub] of var bool: t0;
          array[lb+1..ub] of var bool: t1;
        }
        in
        %  first two slices are hard-coded
        (t1[lb+1] == (x[lb] /\ x[lb+1])) /\
        (t0[lb+1] == not t1[lb+1]) /\
        %   remaining slices are regular
        forall(i in lb+2..ub)
        (
          (t0[i] == (t0[i-1] != x[i]) \/ (t0[i-1] /\ t1[i-1])) /\
          (t1[i] == t1[i-1] \/ (t0[i-1] /\ x[i])) 
        ) /\
        %  output of final slice must be  1 0 to fulfil predicate
        (t1[ub] /\ not t0[ub])
      )
    endif endif;

问题：

Does it make sense to use home-grown cardinality predicates? Or is the MiniZinc implementation of sum() beyond all doubts in terms of solution speed?

更新：
我正在使用 Gecode 作为求解器后端。

Answer 1

线性求和通常是在约束求解器中实现良好的最重要约束之一，因此对于您的情况，使用简单求和的初始版本要好得多。特别是，Gecode 中实现布尔求和的传播器经过大量优化以尽可能高效。

一般来说，使用可用的约束通常是个好主意。特别是，如果一个人正在做的事情很好地映射到 global constraint that is typically a good idea. A related example would be if you want to count the occurrences of several different numbers in an array of integers, in which case the global cardinality constraint 是非常有用的。

为了完整性：当使用惰性子句生成求解器（例如 Chuffed）时，（新颖的）分解有时可能非常有用。但这是一个更高级的话题。

MiniZinc 中的基数约束

Cardinality constraints in MiniZinc

constraint-programming

minizinc

gecode