Initial constraint propagation

Constraint propagation is a powerful technique used by CP Optimizer in the search for solutions to constraint programming problems. The initial constraint propagation removes values from domains that will not take part in any solution.

First, the CP Optimizer engine performs an initial constraint propagation. The initial constraint propagation removes values from domains that will not take part in any solution. Before propagation, the domains are:

D(x) = [5 6 7 8 9 10 11 12]
D(y) = [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17]

To get an idea of how initial constraint propagation works, consider the constraint x + y = 17. If you take the smallest number in the domain of x, which is 5, and add it to the largest number in the domain of y, which is 17, the answer is 22. This combination of values (x = 5, y = 17) violates the constraint x + y = 17. The only value of x that would work with y = 17 is x = 0. However, there is no value of 0 in the domain of x, so y cannot be equal to 17. The value y = 17 cannot take part in any solution. The domain reduction algorithm employed by the constraint propagation engine removes the value y = 17 from the domain of y. Similarly, the propagation engine removes the following values from the domain of y: 13, 14, 15 and 16.

Likewise, if you take the largest number in the domain of x, which is 12, and add it to the smallest number in the domain of y, which is 2, the answer is 14. This combination of values (x = 12, y = 2) violates the constraint x + y = 17. The only value of x that would work with y = 2 is x = 15. However, there is no value of 15 in the domain of x, so y cannot be equal to 2. The value of y = 2 cannot take part in any solution. the propagation engine removes the value y = 2 from the domain of y. For the same reason, the domain reduction algorithm employed by the propagation engine removes the following values from the domain of y: 2, 3 and 4.

After initial propagation for the constraint x + y = 17, the domains are:

D(x) = [5 6 7 8 9 10 11 12]
D(y) = [5 6 7 8 9 10 11 12]

Now, examine the constraint x - y = 5. If you take the value 5 in the domain of x, you can see that the only value of y that would work with x = 5 is y = 0. However, there is no value of 0 in the domain of y, so x cannot equal 5. The value x = 5 cannot take part in any solution. The propagation engine removes the value x = 5 from the domain of x. Using similar logic, the propagation engine removes the following values from the domain of x: 6, 7, 8 and 9. Likewise, the domain reduction algorithm employed by the propagation engine removes the following values from the domain of y: 8, 9, 10, 11 and 12.

Returning to the other constraint, there are no further values that can be removed from the variables. After initial propagation, the search space has been reduced in size. The domains are now:

D(x) = [10 11 12]
D(y) = [5 6 7]