Global Constraint Catalog: sec3.7.59

3.7.59. Constructive disjunction

A constraint for which a filtering algorithm uses constructive disjunction. Constructive disjunction [VanHentenryckSaraswatDeville95], [WurtzMuller96] is a technique for handling in an active way a set of disjunctive constraints. It consists to try out each alternative of a disjunction and then to remove values that were pruned in all alternatives. Table 3.7.14 illustrates this technique in the context of a non-overlapping constraint between two rectangles (i.e., a special case of the $𝚝𝚠𝚘_𝚘𝚛𝚝𝚑_𝚍𝚘_𝚗𝚘𝚝_𝚘𝚟𝚎𝚛𝚕𝚊𝚙$ constraint). The first rectangle $R_{1}$ has a width of 3 and a height of 2, while the second rectangle $R_{2}$ has a width of 2 and a height of 5. The coordinates $(x_{1}, y_{1})$ of the lower leftmost corner of $R_{1}$ have to be respectively located within intervals $[3, 5]$ and $[6, 7]$ . Similarly the coordinates $(x_{2}, y_{2})$ of the lower leftmost corner of $R_{2}$ have to be located within $[2, 4]$ and $[3, 4]$ .

**Table 3.7.14.** Illustrating *constructive disjunction* in the context of a non-overlapping constraint between two rectangles.
Hypothesis regarding the respective position of $R_{1}$ and $R_{2}$
$R_{2}$ before $R_{1}$ :	$R_{2}$ after $R_{1}$ :	$R_{2}$ below $R_{1}$ :	$R_{2}$ on top of $R_{1}$ :
$X_{2} + 2 \leq X_{1}$	$X_{1} + 3 \leq X_{2}$	$Y_{2} + 5 \leq Y_{1}$	$Y_{1} + 2 \leq Y_{2}$
$[2, 4] + 2 \leq [3, 5]$	$[3, 5] + 3 \leq [2, 4]$	$[3, 4] + 5 \leq [6, 7]$	$[6, 7] + 2 \leq [3, 4]$
$[2, 3] + 2 \leq [4, 5]$	contradiction	contradiction	contradiction
Removed values from each variable according to each hypothesis
$X_{1} : {3}$	$X_{1} : {3, 4, 5}$	$X_{1} : {3, 4, 5}$	$X_{1} : {3, 4, 5}$
$X_{2} : {4}$	$X_{2} : {2, 3, 4}$	$X_{2} : {2, 3, 4}$	$X_{2} : {2, 3, 4}$
$Y_{1} : \emptyset$	$Y_{1} : {6, 7}$	$Y_{1} : {6, 7}$	$Y_{1} : {6, 7}$
$Y_{2} : \emptyset$	$Y_{2} : {3, 4}$	$Y_{2} : {3, 4}$	$Y_{2} : {3, 4}$
Values finally removed: value 3 from $X_{1}$ and value 4 from $X_{2}$

In the context of the $𝚌𝚊𝚜𝚎$ constraint, constructive disjunction is applied on each sink node of the dag describing the set of solutions (i.e., we remove values that are removed in all the sink nodes).
In the context of the $𝚍𝚒𝚜𝚓𝚞𝚗𝚌𝚝𝚒𝚟𝚎$ (respectively $𝚍𝚒𝚏𝚏𝚗$ ) constraint, constructive disjunction can be applied on each pair of tasks (respectively objects). However, as described in the Algorithm slots of these two constraints, more specific and efficient filtering algorithms exist for both constraints.
In the context of the $𝚐𝚎𝚘𝚜𝚝$ constraint, constructive disjunction is applied on the different potential values of the shape variable of an object in order to prune its coordinates.

Global Constraint Catalog

3. Description of the Catalogue

3.7.59. Constructive disjunction

Table 3.7.14. Illustrating constructive disjunction in the context of a non-overlapping constraint between two rectangles.