Set constraints

Constraints over finite sets of integers. A solver that declares var set of int in its decision types should expect these; one that does not may still accept int_in, whose set argument is constant. That one is named for the integer it restricts; there is no interval form, because a range is a set.

Sets cross the interface as range lists, so a solver never sees an enumerated membership list for a large interval.

There is no set_of_int_superset: it is set_of_int_subset with the arguments the other way round.

20 constraints

int_array_range

int_array_range(list of var int: xs, int: offset, var set of int: domain, var set of int: image)

The image is exactly the set of values the array takes at the given indices.

$$\mathit{image} = \{\, \mathit{xs}_{i - \mathit{offset} + 1} \mid i \in \mathit{domain} \,\}$$

int_array_roots

int_array_roots(list of var int: xs, int: offset, var set of int: values, var set of int: s)

The set holds exactly those indices whose array element lies in the given value set.

$$\forall i : i \in s \leftrightarrow \mathit{xs}_{i - \mathit{offset} + 1} \in \mathit{values}$$

int_array_union

int_array_union(list of var int: xs, var set of int: result)

The result is the set of values the integer array takes.

$$\mathit{result} = \{\, \mathit{xs}_i \mid i \,\}$$

int_in

int_in(var int: x, var set of int: values)

also declarable as int_in_reif and int_in_imp

The integer is a member of the set.

$$x \in \mathit{values}$$

Declared with both sides variable, which is the general case. A solver that only supports a constant set says so by declaring values as a parameter; it is then the application’s job not to reach for it when the set is a decision variable. Against a constant set this says the same thing as restricting the variable’s decision_domain, but as a posted constraint rather than a declaration.

int_set_channel

int_set_channel(list of var int: ints, int: int_offset, list of var set of int: sets, int: set_offset)

also declarable as int_set_channel_reif and int_set_channel_imp

Element i of the integer array names a set that contains i, and every such membership is mirrored.

$$\forall i, j : \mathit{ints}_{i - \mathit{int\_offset} + 1} = j \leftrightarrow i \in \mathit{sets}_{j - \mathit{set\_offset} + 1}$$

set_of_int_array_intersect

set_of_int_array_intersect(list of var set of int: xs, var set of int: result)

The result is the intersection of every set in the array.

$$\mathit{result} = \bigcap_{i} \mathit{xs}_i$$

set_of_int_array_union

set_of_int_array_union(list of var set of int: xs, var set of int: result)

The result is the union of every set in the array.

$$\mathit{result} = \bigcup_{i} \mathit{xs}_i$$

set_of_int_card

set_of_int_card(var set of int: s, var int: n)

The count is the number of elements in the set.

$$n = \lvert s \rvert$$

set_of_int_diff

set_of_int_diff(var set of int: s, var set of int: t, var set of int: result)

The result contains the members of the first operand that are not in the second.

$$\mathit{result} = s \setminus t$$

set_of_int_eq

set_of_int_eq(var set of int: s, var set of int: t)

also declarable as set_of_int_eq_reif and set_of_int_eq_imp

The two sets have the same members.

$$s = t$$

set_of_int_intersect

set_of_int_intersect(var set of int: s, var set of int: t, var set of int: result)

The result contains exactly the members common to both operands.

$$\mathit{result} = s \cap t$$

set_of_int_le

set_of_int_le(var set of int: s, var set of int: t)

also declarable as set_of_int_le_reif and set_of_int_le_imp

The first set is no greater than the second in the standard total order on sets.

$$s \preceq t$$

The order compares sets by their smallest differing element. It is total, which is what lets sets be used where an ordering is needed.

set_of_int_lt

set_of_int_lt(var set of int: s, var set of int: t)

also declarable as set_of_int_lt_reif and set_of_int_lt_imp

The first set is strictly less than the second in the standard total order on sets.

$$s \prec t$$

set_of_int_max_overlap

set_of_int_max_overlap(list of var set of int: xs, int: max_overlap)

also declarable as set_of_int_max_overlap_reif and set_of_int_max_overlap_imp

No two sets in the array share more than the given number of members.

$$\forall i < j : \lvert \mathit{xs}_i \cap \mathit{xs}_j \rvert \leq \mathit{max\_overlap}$$

set_of_int_ne

set_of_int_ne(var set of int: s, var set of int: t)

also declarable as set_of_int_ne_reif and set_of_int_ne_imp

The two sets differ in at least one member.

$$s \neq t$$

set_of_int_partition

set_of_int_partition(list of var set of int: xs, set of int: universe)

also declarable as set_of_int_partition_reif and set_of_int_partition_imp

The sets are pairwise disjoint and together cover the universe exactly.

$$\bigcup_{i} \mathit{xs}_i = \mathit{universe} \;\wedge\; \forall i < j : \mathit{xs}_i \cap \mathit{xs}_j = \emptyset$$

set_of_int_subset

set_of_int_subset(var set of int: s, var set of int: t)

also declarable as set_of_int_subset_reif and set_of_int_subset_imp

Every member of the first set is a member of the second.

$$s \subseteq t$$

set_of_int_symdiff

set_of_int_symdiff(var set of int: s, var set of int: t, var set of int: result)

The result contains the members of exactly one of the two operands.

$$\mathit{result} = (s \setminus t) \cup (t \setminus s)$$

set_of_int_to_bool

set_of_int_to_bool(var set of int: s, list of var bool: flags, int: offset)

Each Boolean records whether the corresponding index is a member of the set.

$$\forall i : \mathit{flags}_{i - \mathit{offset} + 1} \leftrightarrow i \in s$$

The standard channelling between a set variable and its characteristic vector.

set_of_int_union

set_of_int_union(var set of int: s, var set of int: t, var set of int: result)

The result contains exactly the members of either operand.

$$\mathit{result} = s \cup t$$