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≀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.