3.7.57. 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.12 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 lefmost 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 lefmost corner of R 2 have to be located within [2,4] and [3,4].

Table 3.7.12. 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≤X 1 X 1 +3≤X 2 Y 2 +5≤Y 1 Y 1 +2≤Y 2
[2,4]+2≤[3,5][3,5]+3≤[2,4][3,4]+5≤[6,7][6,7]+2≤[3,4]
[2,3]+2≤[4,5]contradictioncontradictioncontradiction
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 :∅Y 1 :{6,7}Y 1 :{6,7}Y 1 :{6,7}
Y 2 :∅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.