4.2.2.5. Counting constraints

These constraints count and restrict how many times certain values occur in an array of variables. MiniZinc will automatically generate the basic counting constraints below from expressions such as count(i in x)(i=c) <= d, so you can write models in this much more readable style instead of using these predicates. However, if your model contains multiple counting constraints over the same array, constraints like distribute or global_cardinality below may be useful.

In this section: among, at_least, at_most, at_most1, count, count_eq, count_geq, count_gt, count_leq, count_lt, count_neq, distribute, exactly, global_cardinality, global_cardinality_closed.

among

1.  predicate among(var int: n, array [$X] of var $$E: x, set of $$E: v)

2.  function var int: among(array [$X] of var $$E: x, set of $$E: v)
  1. Requires exactly n variables in x to take one of the values in v.

  2. Returns the number of variables in x that take one of the values in v.

at_least

predicate at_least(int: n,
                   array [$X] of var set of $$E: x,
                   set of $$E: v)
Requires at least n variables in x to take the value v.

at_most

predicate at_most(int: n,
                  array [$X] of var set of $$E: x,
                  set of $$E: v)
Requires at most n variables in x to take the value v.

at_most1

predicate at_most1(array [$X] of var set of int: s)
Requires that each pair of sets in s overlap in at most one element.

count

1.  function var int: count(array [$X] of var $$E: x, var $$E: y)

2.  predicate count(array [$X] of var $$E: x, var $$E: y, var int: c)
  1. Returns the number of occurrences of y in x.

  2. Constrains c to be the number of occurrences of y in x.

count_eq

1.  predicate count_eq(array [$X] of var $$E: x, var $$E: y, var int: c)

2.  predicate count_eq(array [$X] of var $$E: x, $$E: y, int: c)

3.  function var int: count_eq(array [$X] of var $$E: x, var $$E: y)
1, 2.
Constrains c to be the number of occurrences of y in x.
  1. Returns the number of occurrences of y in x.

count_geq

predicate count_geq(array [$X] of var $$E: x, var $$E: y, var int: c)
predicate count_geq(array [$X] of var $$E: x, $$E: y, int: c)
Constrains c to be greater than or equal to the number of occurrences of y in x.

count_gt

predicate count_gt(array [$X] of var $$E: x, var $$E: y, var int: c)
predicate count_gt(array [$X] of var $$E: x, $$E: y, int: c)
Constrains c to be strictly greater than the number of occurrences of y in x.

count_leq

predicate count_leq(array [$X] of var $$E: x, var $$E: y, var int: c)
predicate count_leq(array [$X] of var $$E: x, $$E: y, int: c)
Constrains c to be less than or equal to the number of occurrences of y in x.

count_lt

predicate count_lt(array [$X] of var $$E: x, var $$E: y, var int: c)
predicate count_lt(array [$X] of var $$E: x, $$E: y, int: c)
Constrains c to be strictly less than the number of occurrences of y in x.

count_neq

predicate count_neq(array [$X] of var $$E: x, var $$E: y, var int: c)
predicate count_neq(array [$X] of var $$E: x, $$E: y, int: c)
Constrains c to be not equal to the number of occurrences of y in x.

distribute

1.  predicate distribute(array [$X] of var int: card,
                         array [$X] of var int: value,
                         array [$Y] of var int: base)

2.  function array [$X] of var int: distribute(array [$X] of var int: value,
                                               array [$Y] of var int: base)
  1. Requires that card[i] is the number of occurrences of value[i] in base. The values in value need not be distinct.

  2. Returns an array of the number of occurrences of value[i] in base. The values in value need not be distinct.

exactly

predicate exactly(int: n,
                  array [$X] of var set of $$E: x,
                  set of $$E: v)
Requires exactly n variables in x to take the value v.

global_cardinality

1.  predicate global_cardinality(array [$X] of var int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of var int: counts)

2.  predicate global_cardinality(array [$X] of var opt int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of var int: counts)

3.  predicate global_cardinality(array [$X] of var int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of int: lbound,
                                 array [$Y] of int: ubound)

4.  predicate global_cardinality(array [$X] of var opt int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of int: lbound,
                                 array [$Y] of int: ubound)

5.  predicate global_cardinality(array [$X] of var set of int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of var int: counts)

6.  predicate global_cardinality(array [$X] of var set of int: x,
                                 array [$Y] of int: cover,
                                 array [$Y] of int: lbound,
                                 array [$Y] of int: ubound)

7.  function array [$Y] of var int: global_cardinality(array [$X] of var int: x,
                                                       array [$Y] of int: cover)
1, 2.
Requires that the number of occurrences of cover[i] in x is counts[i].
3, 4.
Requires that for all i, the value cover[i] appears at least lbound[i] and at most ubound[i] times in the array x.
  1. Requires that the number of occurrences of cover[i] in x is counts[i].

  2. Requires that for all i, the value cover[i] appears at least lbound[i] and at most ubound[i] times in the array x.

  3. Returns the number of occurrences of cover[i] in x.

global_cardinality_closed

1.  predicate global_cardinality_closed(array [$X] of var int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of var int: counts)

2.  predicate global_cardinality_closed(array [$X] of var opt int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of var int: counts)

3.  predicate global_cardinality_closed(array [$X] of var int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of int: lbound,
                                        array [$Y] of int: ubound)

4.  predicate global_cardinality_closed(array [$X] of var opt int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of int: lbound,
                                        array [$Y] of int: ubound)

5.  predicate global_cardinality_closed(array [$X] of var set of int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of var int: counts)

6.  predicate global_cardinality_closed(array [$X] of var set of int: x,
                                        array [$Y] of int: cover,
                                        array [$Y] of int: lbound,
                                        array [$Y] of int: ubound)

7.  function array [$Y] of var int: global_cardinality_closed(array [$X] of var int: x,
                                                              array [$Y] of int: cover)
  1. Requires that the number of occurrences of cover[i] in x is counts[i].

    The elements of x must take their values from cover.

  2. Requires that the number of occurrences of cover[i] in x is counts[i].

    The elements of x must take their values from cover or be absent.

  3. Requires that for all i, the value cover[i] appears at least lbound[i] and at most ubound[i] times in the array x.

    The elements of x must take their values from cover.

  4. Requires that for all i, the value cover[i] appears at least lbound[i] and at most ubound[i] times in the array x.

    The elements of x must take their values from cover or be absent.

  5. Requires that the number of occurrences of cover[i] in x is counts[i].

    The elements of x must take their values from cover or be absent.

  6. Requires that for all i, the value cover[i] appears at least lbound[i] and at most ubound[i] times in the array x.

    The elements of x must take their values from cover or be absent.

  7. Returns an array with number of occurrences of cover[i] in x.

    The elements of x must take their values from cover.