Global Constraints
Definition(s)
an expressive and concise condition involving a non-fixed number of variables
allDifferent($x_1,x_2,\dots$)
Definition(s)
a constraint C is often called “global” when “processing” as a whole gives better results than “processing” any conjunction of constraints that is “semantically equivalent” to C
allDifferent($x_1,x_2,x_3$) $\iff (x_1\neq x_2) \land (x_2\neq x_3) \land (x_3\neq x_1)$
Example of constraints
cumulative(starts, durations, heights, capacity)
Example of constraints
binpacking(bins, weigths, capacity)
Example of constraints
circuit(successors)
Some cardinality constraints
| Syntax | Definition |
|---|---|
m.allDifferent(X) |
$x_i\neq x_j, \forall i< j$ |
m.among(n, X, v) |
$|x_i : x_i \cap v\neq \emptyset | = n$ |
m.count(y, X, n) |
$ | \{ x_i : x_i = y \} | = n$ |
m.nValues(X, n) |
$|x_i| = n$ |
Notations
- Arrays: $X=\langle x_0, x_1,\ldots\rangle$
- Index: $ 0 \leq i < |X|$
Some connection constraints
| Syntax | Definition |
|---|---|
m.element(v, X, i, o) |
$\exists i : v = x_{i - o}$ |
m.argmax(i, o, X) |
$i \in \{j - o : x_j = \max\{x_k\}\}$ |
m.argmin(i, o, X) |
$i \in \{j - o : x_j = \max\{x_k\}\}$ |
m.max(m, X) |
$m = \max\{x_i\}$ |
m.min(m, X) |
$m = \min\{x_i\}$ |
m.inverseChanneling(X, Y) |
$ \forall i: x_i = j \iff y_j = i \quad (|X| = |Y|)$ |
Notations
- Arrays: $X=\langle x_0, x_1,\ldots\rangle$
- Index: $ 0 \leq i < |X|$
Some Packing and Scheduling constraints
| Syntax | Definition |
|---|---|
m.binPacking(X, S, L, o) |
$ \forall b \in \{x_i\},\sum_{i : x_i = b} S_i \leq L_b$ |
m.cumulative(A, H, c) |
$ \forall t \in \mathcal{N},\sum\{h_i : a^s_i \leq t < a^e_i\} \leq c$ |
m.diffN(X, Y, W, H, true) |
$\forall i<j, x_{i} + w_{i} \leq x_{j} \lor x_{j} + h_{j} ≤ x_{i}$ $\quad\quad\quad \lor y_{i} + h_{i} \leq y_{j} \lor y_{j} + w_{j} ≤ y_{i}$ |
m.knapsack(O, W, E, w, e) |
$\sum_{i} w_i \times O_i = w \land \sum_{i} e_i \times O_i = e$ |
Notations
- Arrays: $X=\langle x_0, x_1,\ldots\rangle$
- Index: $ 0 \leq i < |X|$
- Task (or activity): $a^s + a^d = a^e$
Some Graph-based constraints
| Syntax | Definition |
|---|---|
m.circuit(X) |
$\{(i, x_i) : i \neq x_i\}$ forms a circuit of size $> 1$ |
m.path(X, s, e) |
$\{(i, x_i) : i \neq x_i\}$ forms a path from $s$ to $e$ |
m.tree(X, n) |
$\{(i, x_i) : i \neq x_i\}$ is partitioned into $n$ anti-arborescences |
Notations
- Arrays: $X=\langle x_0, x_1,\ldots\rangle$
- Index: $ 0 \leq i < |X|$
- A pair $(i, x_i)$ represents an arc in a graph induced by $X$
Magic Sequence
A magic series of length $n$ is a sequence of integers $[x_0, …, x_{n-1}]$ between $0$ and $n-1$, such that for all $i \in \{0 , …, n-1\}$, the number $i$ occurs exactly $x_i$ times in the sequence.
For instance, $[1,2,1,0]$ is a magic series of length $4$ :
- value 0 occurs once
- value 1 occurs twice
- value 2 occurs once
- value 3 does not occur
Write a CP model in java using the Choco solver to find magic series for any given n.